点击打开链接uva 11624
思路:bfs
分析:
1 题目要判断joe是否可以逃出迷宫,如果可以输出最小的时间,否则输出impossible
2 题目明确规定有且仅有一个Joe,但是火的个数是不确定的
3 那么如果没有火,我们只要去求Joe走出迷宫的时间即可。但是如果有火的话这里将碰到火在蔓延并且人在走,但是对于火来说我们可以先预处理出每一个可以着火的点的着火时间,然后在利用bfs搜索只有当前这个结点的着火时间大于人到的时间我们才加入队列
4 所以我们只需要两次的bfs即可
代码:
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
struct Node{
int x;
int y;
int t;
};
Node start;
char maze[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int timeState[MAXN][MAXN];
int n , m;
queue<Node>q;
bool ok(int x , int y){
if(x >= 0 && x < n && y >= 0 && y < m)
return true;
return false;
}
//初始化并且预处理每个点的着火的时间
void init(){
//找起始点
bool isFire = false;
while(!q.empty())
q.pop();
memset(timeState , INF , sizeof(timeState));
memset(vis , false , sizeof(vis));
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
if(maze[i][j] == 'J'){
start.x = i;
start.y = j;
start.t = 0;
}
if(maze[i][j] == 'F'){
isFire = true;
vis[i][j] = true;
timeState[i][j] = 0;
q.push((Node){i,j,0});
}
}
}
if(!isFire)
return;
//预处理出每一个点的着火的时间
while(!q.empty()){
Node tmp = q.front();
q.pop();
for(int i = 0 ; i < 4 ; i++){
int tx = tmp.x + dir[i][0];
int ty = tmp.y + dir[i][1];
if(ok(tx , ty) && !vis[tx][ty] && maze[tx][ty] == '.'){
vis[tx][ty] = true;
timeState[tx][ty] = tmp.t+1;;
q.push((Node){tx , ty , tmp.t+1});
}
}
}
}
int solve(){
while(!q.empty())
q.pop();
q.push(start);
memset(vis , false , sizeof(vis));
vis[start.x][start.y] = true;
//广搜
while(!q.empty()){
Node tmp = q.front();
q.pop();
//进行四个方向的遍历
for(int i = 0 ; i < 4 ; i++){
int tx = tmp.x + dir[i][0];
int ty = tmp.y + dir[i][1];
if(!ok(tx , ty))
return tmp.t+1;
if(!vis[tx][ty] && maze[tx][ty] == '.' && tmp.t+1 < timeState[tx][ty]){
q.push((Node){tx , ty , tmp.t+1});
vis[tx][ty] = true;
}
}
}
return INF;
}
int main(){
int Case;
scanf("%d" , &Case);
while(Case--){
scanf("%d%d%*c" , &n , &m);
for(int i = 0 ; i < n ; i++)
gets(maze[i]);
init();
int ans = solve();
if(ans != INF)
printf("%d\n" , ans);
else
puts("IMPOSSIBLE");
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
UVa Online Judge(ACM-ICPC Live Archive)、hackerrank、Leetcode.com的算法问题解决方案 使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列...