ztrztr 的博客 - BFS
type: channel
link: https://typecho.ztrztr.top/tag/bfs/
items: 模拟测验（零）水灾 做题笔记

模拟测验（零）水灾 做题笔记
type: item
date: 2024-06-03T00:59:51+08:00
description: 题面思路这道题第一眼应该可以看出是一道搜索的题目。我们先用 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 ++) { …