本文主要是介绍uva11624 fire bfs 最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// uva11624 bfs最短路
// Fire 给你一个图，有一个起点'J'，从任何边界走出去就算成功
// 但是，会有起火的地方，每秒火会上下左右四个方向蔓延，人不能
// 走有火的地方，问能不能逃出去，逃出去的最少步数是多少
//
// 我的思路就是先预处理出每个地方的火的燃烧的最开始的时间
// 这bfs就可以了，计为f[i][j];
// 之后的再走一遍最短路，用s[i][j]记录人所能达到的最早的时间
// 走不到为-1，则，最后只要判断边界上能走到的就ok了
// 优化就是当走的点的最少时间比着火的时间小的时候就就放进去
// 最后，就ac啦~
//
// 哎，wa了好几发了，先开始没有用s[i][j]记录最短时间，最后导致
// TLE了好几发，用自定义的队列也是TLE，猛然想到，如果当前已经走到的
// 点是最短的直接记录就ok了，不用再去走，这是一个重要的剪枝。
//
// 搜索的道路刚刚开始，继续练吧。。。#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define ceil(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define gcd __gcd
#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))
#define popCount __builtin_popcountll
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const long double PI = acos(-1.L);template<class T> inline T lcm(const T& a, const T& b) { return a/gcd(a, b)*b; }
template<class T> inline T lowBit(const T& x) { return x&-x; }
template<class T> inline T maximize(T& a, const T& b) { return a=a<b?b:a; }
template<class T> inline T minimize(T& a, const T& b) { return a=a<b?a:b; }const int maxn = 1008;
char mp[maxn][maxn];
int n,m;
int f[maxn][maxn];
int s[maxn][maxn];
struct node {int x;int y;
// int time;
};
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
node que[maxn*maxn*10*10];
void print(){for (int i=0;i<n;i++){for (int j=0;j<n;j++)printf("%d ",f[i][j]);puts("");}puts("");
}
void init(){scanf("%d%d",&n,&m);for (int i=0;i<n;i++)for (int j=0;j<m;j++)f[i][j]=-1;//print();for (int i=0;i<n;i++)scanf("%s",mp[i]);//queue<node> q;int head = 0,tail=0;for (int i=0;i<n;i++)for (int j=0;j<m;j++)if (mp[i][j]=='F'){f[i][j]=0;que[tail++]=(node){i,j};}while(head<tail){node x = que[head++];// f[x.x][x.y] = x.time;//q.push()//q.pop();for (int i=0;i<4;i++){int tx = x.x + dx[i];int ty = x.y + dy[i];if (tx>=0&&tx<n&&ty>=0&&ty<m&&mp[tx][ty]=='.'&&f[tx][ty]==-1){f[tx][ty]=f[x.x][x.y]+1;que[tail++]=(node){tx,ty};}}}// print();
}void solve(){node now ;for (int i=0;i<n;i++)for (int j=0;j<m;j++)s[i][j]=-1;for (int i=0;i<n;i++)for (int j=0;j<m;j++)if (mp[i][j]=='J'){now.x = i;now.y = j;s[i][j]=0;}
// now.time = 0;
// queue<node> q;int head=0,tail=0;que[tail++]=now;int time = -1;while(head<tail){node x = que[head++];// s[x.x][x.y]=x.time;//q.pop();if (x.x==0||x.x==n-1||x.y==0||x.y==m-1){time = s[x.x][x.y]+1;break;}for (int i=0;i<4;i++){int tx = x.x + dx[i];int ty = x.y + dy[i];if (s[tx][ty]!=-1) continue;if (tx>=0 && tx<n && ty>=0 && ty<m && mp[tx][ty]=='.' && (s[x.x][x.y]+1<f[tx][ty] || f[tx][ty]==-1)){s[tx][ty] = s[x.x][x.y]+1;que[tail++]=(node){tx,ty};}}}if (time==-1){printf("IMPOSSIBLE");}else {printf("%d",time);}puts("");}int main() {int t;//freopen("G:\\Code\\1.txt","r",stdin);scanf("%d",&t);while(t--){init();solve();}return 0;
}
这篇关于uva11624 fire bfs 最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
