Giả sử chúng ta có một cây không hướng bao gồm n đỉnh. Các đỉnh được đánh số từ 1 đến n. Một con ếch bắt đầu nhảy từ đỉnh 1. Con ếch có thể nhảy từ đỉnh hiện tại sang một đỉnh chưa thăm lân cận trong một giây. Con ếch không thể nhảy trở lại đỉnh đã thăm. Nếu ếch có thể nhảy đến nhiều đỉnh, nó sẽ chọn ngẫu nhiên một trong số chúng với xác suất như nhau, ngược lại, khi ếch không thể nhảy đến đỉnh chưa thăm nào, nó sẽ ở lại đỉnh đó mãi mãi.
Cây được cho dưới dạng mảng các cạnh. Chúng ta cần tìm xác suất rằng sau t giây ếch đang ở đỉnh target.
Ví dụ, nếu đầu vào là n = 7, t = 2, target = 4 và cây như sau:
Thì đầu ra sẽ là 0.1666. Từ đồ thị, ếch bắt đầu tại đỉnh 1, nhảy đến đỉnh 2 sau giây 1 với xác suất 0.3333, sau đó nhảy đến đỉnh 4 sau giây 2 với xác suất 0.5. Do đó xác suất ếch ở đỉnh 4 sau 2 giây là 0.3333 * 0.5 = 0.16665.
Giải pháp
Để giải bài toán này, ta thực hiện các bước sau:
- Khởi tạo ret = 1
- Định nghĩa tập hợp visited
- Định nghĩa hàm dfs() nhận tham số: node, start, danh sách cạnh g, time, t, stack st
- Nếu node đã có trong visited, trả về false
- Thêm node vào visited
- Nếu node == 1: tt = time, ok = true, trả về true
- Duyệt qua các đỉnh kề của node, đẩy vào stack và gọi đệ quy dfs
- Từ hàm main: xây dựng đồ thị, gọi dfs(target, target, graph, 0, t, st)
- Duyệt stack để tính xác suất: với mỗi node, sz = bậc của node (giảm 1 nếu không phải gốc), ret *= 1.0/sz
- Kiểm tra điều kiện: nếu tt > t trả về 0; nếu tt == t trả về ret; nếu tt < t và target == 1 và bậc >= 1 trả về 0; ngược lại trả về ret nếu target là lá, ngược lại 0
Ví dụ mã C++
#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;
}
};
int 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));
return 0;
}
Đầu vào
7, {{1,2},{1,3},{1,7},{2,4},{2,6},{3,5}}, 2, 4
Đầu ra
0.166667