这道题是BFS(DFS也可以,但要剪枝,优化)
注意的要点:
1.此题检查数组范围,不要太大,2000会爆
2.向四周蔓延->不是八个方向,而是上下左右四个方向(描述不清)重点(我被这个难了好长时间)
3.注意判断等于情况,搜索时注意是人先离开,还是岩浆先到
4.注意为多组输入,每次都要将全局变量初始化为0,否则会出问题
思路:双向广搜(不要被名字吓到)
先搜索岩浆到每一个格子的步数
再搜索人行动时的步数,并在过程中比较大小,并取消不合理的搜索
可以理解为搜索两个人在不同的起点出发,互相追逐
#include<bits/stdc++.h> using namespace std; int vis[1100][1100],n,m,sx,sy,fx,fy,qx,qy,step[1100][1100]; int fire[1100][1100]; char mp[1100][1100]; int dir[4][2]={0,1,1,0,-1,0,0,-1}; struct node { int x,y; }; void getfire(int qx,int qy) { queue<node>q; node start,next; start.x=qx; start.y=qy; vis[qx][qy]=1; fire[qx][qy]=0; q.push(start); while(!q.empty()) { start=q.front(); q.pop(); for(int i=0;i<4;i++) { next.x=start.x+dir[i][0]; next.y=start.y+dir[i][1]; if(next.x<1||next.x>n||next.y<1||next.y>m) continue; if(vis[next.x][next.y]==0) { vis[next.x][next.y]=1; q.push(next); fire[next.x][next.y]=fire[start.x][start.y]+1; } } } return; } bool bfs(int sx,int sy) { queue<node>q; node start,next; start.x=sx; start.y=sy; q.push(start); vis[sx][sy]=1; while(!q.empty()) { start=q.front(); q.pop(); if(start.x==fx&&start.y==fy) return true; if(step[start.x][start.y]>=fire[start.x][start.y]) continue; for(int i=0;i<4;i++) { next.x=start.x+dir[i][0]; next.y=start.y+dir[i][1]; if(next.x<1||next.x>n||next.y<1||next.y>m) continue; if(step[start.x][start.y]+1>fire[next.x][next.y]) continue; if(vis[next.x][next.y]||mp[next.x][next.y]=='#') continue; q.push(next); vis[next.x][next.y]=1; step[next.x][next.y]=step[start.x][start.y]+1; } } return false; } int main() { int i,j; while(cin>>n>>m) { for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>mp[i][j]; if(mp[i][j]=='S') { sx=i; sy=j; } if(mp[i][j]=='E') { fx=i; fy=j; } if(mp[i][j]=='F') { qx=i; qy=j; } } } memset(vis,0,sizeof(vis)); memset(step,0,sizeof(step)); memset(fire,0,sizeof(fire)); getfire(qx,qy); memset(vis,0,sizeof(vis)); if(bfs(sx,sy)) cout<<"PIG PIG PIG!"<<endl; else cout<<"A! WO SI LA!"<<endl; } return 0; }