题目链接：https://ac.nowcoder.com/acm/contest/301/G
我的写法是将岩浆和小乐乐加入到队列里一起搜索(先让岩浆入队)，需要注意的是岩浆可以覆盖'#'，所以它可能会比小乐乐先到达某一点，所以对于两者的判断需要分开来判断，还有就是要开vis数组去标记，不能直接将走过的点变为'#'，因为岩浆可以走'#'，所以在搜的时候岩浆可能会死循环，这一点没注意到，罚时爆炸。后台数据略水，对于下面这个样例，跑错了但是可以AC..
AC代码：
代码语言：javascript复制#include <bits/stdc .h>
#define maxn 1005
using namespace std;
struct Node{
int x,y,step;
bool flag;
}fire,Now,Next,E;
char str[maxn][maxn];
bool vis[maxn][maxn];
int dir[4][2] = {1,0, 0,1, -1,0, 0,-1};
int n,m,E_x,E_y,flag1;
bool Check(int xx, int yy){
if(xx>=0&&yy>=0&&xx<n&&yy<m&&str[xx][yy]!='#'&&vis[xx][yy] == false){
return true;
}
return false;
}
bool Check1(int xx,int yy){
if(xx>=0&&yy>=0&&xx<n&&yy<m&&vis[xx][yy] == false){
return true;
}
return false;
}
bool bfs(){
queue<Node> q;
q.push(fire);
q.push(Now);
while(!q.empty()){
Now = q.front();
q.pop();
if(Now.flag == false && Now.x == E_x && Now.y == E_y)
return false;
if(Now.flag == true && Now.x == E_x && E_y == Now.y)
return true;
for(int i=0;i<4;i ){
Next.x = Now.x dir[i][0];
Next.y = Now.y dir[i][1];
if(Now.flag == true && Check(Next.x, Next.y)){
vis[Next.x][Next.y] = true;
Next.step = Now.step 1;
Next.flag = true;
q.push(Next);
}
if(Now.flag == false && Check1(Next.x,Next.y)){
Next.step = Now.step 1;
vis[Next.x][Next.y] = true;
Next.flag = false;
q.push(Next);
}
}
}
return false;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
for(int i=0;i<n;i ){
cin>>str[i];
}
memset(vis,false,sizeof(vis));
flag1 = true;
for(int i=0;i<n;i ){
for(int j=0;j<m;j ){
if(str[i][j] == 'S'){
Now.x = i;
Now.y = j;
Now.step = 0;
Now.flag = true;
}
if(str[i][j] == 'F'){
fire.x = i;
fire.y = j;
fire.step = 0;
fire.flag = false;
}
if(str[i][j] == 'E'){
E_x = i;
E_y = j;
}
}
}
if(!bfs()){
puts("A! WO SI LA!");
}
else{
puts("PIG PIG PIG!");
}
}
return 0;
}
