Giả sử chúng ta có một cây vô hướng gồm n đỉnh. Các đỉnh được đánh số từ 1 đến n. Bây giờ một con ếch bắt đầu nhảy từ đỉnh 1. Con ếch có thể nhảy từ đỉnh hiện tại của nó sang một đỉnh khác không được thăm nếu chúng ở gần nhau, trong một giây. Con ếch không thể nhảy trở lại đỉnh đã thăm. Trong trường hợp con ếch có thể nhảy đến một số đỉnh, nó sẽ nhảy ngẫu nhiên đến một trong số chúng
trong đó xác suất là như nhau, ngược lại, khi con ếch không thể nhảy đến bất kỳ đỉnh nào chưa được thăm, nó sẽ nhảy mãi mãi trên cùng một đỉnh.
Cây được cho dưới dạng một mảng các cạnh. Chúng ta phải tìm xác suất để sau t giây con ếch ở trên mục tiêu đỉnh.
Vì vậy, nếu đầu vào giống như n là 7, t là 2, mục tiêu là 4 và cây giống như -
thì đầu ra sẽ là 0,1666, như từ biểu đồ. Con ếch bắt đầu ở đỉnh 1, nhảy với xác suất 0,3333 đến đỉnh 2 sau giây 1 và sau đó nhảy với xác suất 0,5 đến đỉnh 4 sau giây 2. Như vậy xác suất để con ếch ở trên đỉnh 4 sau 2 giây là 0,3333 * 0,5 =1,6665.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ret:=1
-
Xác định một tập hợp đã truy cập
-
Xác định một hàm dfs (), hàm này sẽ lấy nút, bắt đầu, danh sách các cạnh g, thời gian, t, một ngăn xếp st,
-
nếu nút là thành viên của đã truy cập, thì -
-
trả về false
-
-
chèn nút vào đã truy cập
-
nếu nút giống 1, thì -
-
tt:=time, ok:=true
-
trả về true
-
-
để khởi tạo i:=0, khi tôi
-
chèn g [node, i] vào st
-
nếu dfs (g [node, i], start, g, time + 1, t, st) là true thì -
-
trả về true
-
-
xóa phần tử khỏi st
-
-
trả về false
-
Từ phương thức chính, hãy làm như sau -
-
ret:=1
-
ok:=false
-
Xác định đồ thị mảng danh sách có kích thước n + 1
-
Xác định một mảng danh sách graph2 có kích thước n + 1
-
để khởi tạo i:=0, khi i
-
chèn các cạnh [i, 1] vào cuối biểu đồ [edge [i, 0]]
-
chèn các cạnh [i, 0] vào cuối biểu đồ [edge [i, 1]]
-
-
Xác định một ngăn xếp
-
dfs (target, target, graph, 0, t, st)
-
while (not st là trống), do -
-
node:=phần tử trên cùng của st
-
sz:=kích thước của biểu đồ [node]
-
nếu nút không bằng 1, thì -
-
(giảm sz đi 1)
-
-
ret:=ret * (1.0 / sz)
-
xóa phần tử khỏi st
-
-
nếu tt> t, thì -
-
trả về 0
-
-
nếu tt giống với t, thì -
-
trả lại ret
-
-
nếu tt
=1 thì - -
trả về 0
-
-
return (nếu tt
1 thì là 0, ngược lại thì ret)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
double ret = 1;
bool ok;
set<int> visited;
int tt;
bool dfs(int node, int start, vector<int> g[], int time, int t,
stack<int>& st){
if (visited.count(node))
return false;
visited.insert(node);
if (node == 1) {
tt = time;
ok = true;
return true;
}
for (int i = 0; i < g[node].size(); i++) {
st.push(g[node][i]);
if (dfs(g[node][i], start, g, time + 1, t, st))
return true;
;
st.pop();
}
return false;
}
double frogPosition(int n, vector<vector<int> >& edges, int t,
int target){
ret = 1;
ok = false;
vector<int> graph[n + 1];
vector<int> graph2[n + 1];
for (int i = 0; i < edges.size(); i++) {
graph[edges[i][0]].push_back(edges[i][1]);
graph[edges[i][1]].push_back(edges[i][0]);
}
stack<int> st;
dfs(target, target, graph, 0, t, st);
while (!st.empty()) {
int node = st.top();
double sz = (double)graph[node].size();
if (node != 1)
sz--;
ret *= (1.0 / sz);
st.pop();
}
if (tt > t)
return 0;
if (tt == t)
return ret;
if (tt < t && target == 1 && graph[target].size() >= 1)
return 0;
return tt < t && graph[target].size() > 1 ? 0 : ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}};
cout << (ob.frogPosition(7,v,2,4));
} Đầu vào
7, {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}, 2, 4 Đầu ra
0.166667