UVa一道题,求大牛帮忙看哪里错了
UVa11624
原题链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2671
应该是简单的BFS,但总是WA,输入样例过了,实在查不出错来,求大牛们帮帮忙!
以下是我的代码:
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int a[4]={-1,1,0,0};
const int b[4]={0,0,-1,1};
char map[1005][1005];
int m[1005][1005];
int main()
{
int t,r,c;
scanf("%d",&t);
int i,j,k,l;
for (i=0;i<t;i++) {
memset(map,'0',sizeof(map));
memset(m,0,sizeof(m));
queue <int> qf;
queue <int> qj;
bool bj=0;
scanf("%d%d",&r,&c);
for (j=0;j<r;j++)
scanf("%s",&map[j]);
for (j=0;j<r;j++)
for (k=0;k<c;k++){
if (map[j][k]=='#')
m[j][k]=-1;
else if (map[j][k]=='J')
qj.push(j*c+k);
else if (map[j][k]=='F'){
qf.push(j*c+k);
m[j][k]=-1;
}
}
while (!qj.empty())
{
int x,y;
int step=m[qj.front()/c][qj.front()%c];
int len=qf.size();
for(j=0;j<len;j++){
x=qf.front()/c;
y=qf.front()%c;
for (k=0;k<4;k++)
if ((m[x+a[k]][y+b[k]]!=-1)&&(x+a[k]<r)&&(x+a[k]>=0)&&(y+b[k]>=0)&&(y+b[k]<c)){
qf.push((x+a[k])*c+y+b[k]);
m[x+a[k]][y+b[k]]=-1;
}
qf.pop();
}
x=qj.front()/c;
y=qj.front()%c;
for (j=0;j<4;j++)
{
int d=x+a[j];
int f=y+b[j];
if (m[d][f]==0){
qj.push(d*c+f);
m[d][f]=step+1;
if (d==0||d==r-1||f==0||f==c-1){
bj=1;
printf("%d\n",m[d][f]+1);
break;
}
}
}
qj.pop();
if (bj==1)
break;
}
if (bj==0)
printf("%s\n","IMPOSSIBLE");
}
return 0;
}
UVa?BFS
[解决办法]
一次BFS总觉得不对。正常应该是先对F做一次BFS确定火烧到每一格要多久,然后再对J做BFS看看能不能逃出去。
给几组数据
2 2
##
JF
5 5
F...#
....#
....#
..J.#
#####
[解决办法]
楼上的是答案,先预处理火烧到没一个的时间,再BFS