题面思路这道题第一眼应该可以看出是一道搜索的题目。我们先用 bfs 搜索一遍，用来计算出洪水到达每一个位置的最少时间。这里需要注意的一点是，有可能有多个洪水的初始地点，所以每一个洪水到达一个地点的时间有可能不一样。所以在更新洪水达到时间的时候，我们需要注意不要直接赋值，要取最小值。第二遍 bfs 是计算能不能达到别墅和最短时间，这个直接 bfs 就行了。在判断是否被洪水追上的时候，我们可以用：if (ti >= tim[i][j]) 来判断。代码#include <bits/stdc++.h> using namespace std; /* bfs 学习 */ int n, m, vis[1005][1005]; char a[1005][1005]; struct node{ int x, y, ti; const bool operator <(const node &x) const{ return x.ti < ti; } }; #define x1 __ #define x2 uysgdfudbuhsdfbvuhdfbvuydfgbvyudfgbyusdgfuisorfg #define y1 ___ #define y2 saigfausygfuysffgoiysfgiufgyufgioyuguiofguifgugfuhg #define x3 ______________sfsdfhsfbs #define y3 ________wigdfuadygfasdgf int tim[55][55]; int dx[105] = {0, 1, 0, -1}; int dy[105] = {1, 0, -1, 0}; int viss[105][105]; #define PII pair <int, int> #define MP make_pair struct nodee{ int x, y, z; }; int x1, x2, y1, y2; void dfs(int si, int sj) { memset(viss, 0, sizeof(viss)); queue <nodee> qwq; // cout << nwi << " " << qwq.push((nodee){si, sj, 0}); int cnttt = 0; while (qwq.size()) { cnttt ++; int ni, nj; ni = qwq.front().x; nj = qwq.front().y; int nt = qwq.front().z; qwq.pop(); // if (cnttt <= 20) cout << ni << " " << nj << " " << nt << "\n"; if (a[ni][nj] == 'X' || a[ni][nj] == 'D') continue; if (viss[ni][nj]) continue; viss[ni][nj] = 1; tim[ni][nj] = min(tim[ni][nj], nt); for (int i = 0; i < 4; i ++ ) { int nx, ny; nx = ni + dx[i]; ny = nj + dy[i]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) qwq.push((nodee){nx, ny, nt + 1}); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); memset(tim, 0x7f, sizeof(tim)); cin >> n >> m; vector <int> x3, y3; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { cin >> a[i][j]; if (a[i][j] == 'S') { x1 = i; y1 = j; } else if (a[i][j] == 'D') { x2 = i; y2 = j; } else if (a[i][j] == '*') { x3.push_back(i); y3.push_back(j); } } } // cout << x3.size() << "\n"; for (int i = 0; i < x3.size(); i ++) { dfs(x3[i], y3[i]); } // for (int i = 1; i <= n; i ++) { // for (int j = 1; j <= m; j ++) { // cout << tim[i][j] << " "; // } // cout << "\n"; // } priority_queue <node> q; q.push((node){x1, y1, 0}); // cout << x2 << " " << y2 << "\n"; while (q.size()) { int i, j; i = q.top().x; j = q.top().y; int ti = q.top().ti; q.pop(); // cout << i << " " << j << " " << ti << "\n"; if (vis[i][j]) continue;; int flag = 0; // for (int ii = 0; i < x3.size(); i ++) { if (ti >= tim[i][j]) { // cout << x3[i] << " " << y3[i] << " " << max(abs(i - x3[i] + 1), abs(j - y3[i] + 1)) << " " << ti - 1 << "\n"; continue; } if (i == x2 && j == y2) { cout << ti; return 0; } // } // if (flag == 1) continue; // if (vis[i][j]) continue; vis[i][j] = 1; if (i >= 1 && i <= n && j >= 1 && j <= m && (a[i + 1][j] == '.' || a[i + 1][j] == 'D')) q.push((node){i + 1, j, ti + 1}); if (i >= 1 && i <= n && j >= 1 && j <= m && (a[i][j + 1] == '.' || a[i][j + 1] == 'D')) q.push((node){i, j + 1, ti + 1}); if (i >= 1 && i <= n && j >= 1 && j <= m && (a[i - 1][j] == '.' || a[i - 1][j] == 'D')) q.push((node){i - 1, j, ti + 1}); if (i >= 1 && i <= n && j >= 1 && j <= m && (a[i][j - 1] == '.' || a[i][j - 1] == 'D')) q.push((node){i, j - 1, ti + 1}); } cout << "ORZ hzwer!!!"; return 0; }