题面

思路

这道题第一眼应该可以看出是一道搜索的题目。

我们先用 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;
}