刚刚开始看到标签,想使用dfs。但是没有写出来(确信),后面去看看博客,发现都用bfs写的,然后试着写了一下。
AC代码
#include<bits/stdc++.h>; using namespace std; int n, m, t; #define Max 35 int move1[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; char mp[Max][Max]; int vis[Max][Max], f[Max][Max];//vis记录是否走过,f记录火焰蔓延至该点的时间 struct node { int x, y; int time; }; int sx, sy, fx, fy;//起点和火源 queue<node>q; void bfs(int x, int y) { queue<node>q; node a, b, temp1, temp2; a.x = x; a.y = y; a.time = 0; q.push(a); while (!q.empty()) { a = q.front(); q.pop(); if (mp[a.x][a.y] == 'E') { cout << a.time << endl; return; } if (f[a.x][a.y] == a.time)continue;//蔓延时间和逃跑时间相等,失败,直接跳出 for (int i = 0;i < 4;i++) { b = a; b.x = a.x + move1[i][0]; b.y = a.y + move1[i][1]; int xx = b.x; int yy = b.y; b.time += 1; if (mp[xx][yy] != '#' && b.time <= f[xx][yy] && !vis[xx][yy] && xx > 0 && xx <= n && yy > 0 && yy <= m) { q.push(b); vis[xx][yy] = 1; } } } cout << "T_T" << endl;//所有路径都走不通,return; return; } int main() { cin >> t; while (t--) { while (!q.empty())q.pop(); memset(vis, 0, sizeof(vis)); cin >> n >> m; for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { cin >> mp[i][j]; if (mp[i][j] == 'S') { sx = i; sy = j; } if (mp[i][j] == '*') { fx = i; fy = j; } } } //将火焰蔓延至每一点的时间计算出来 for (int i = 1;i <= n;i++) { for (int j = 1;j <= m;j++) { f[i][j] = max(abs(fx - i), abs(fy - j)); } } vis[sx][sy] = 1; bfs(sx, sy); } return 0; }