Uestc-1002-解救小Q

BFS题~注意细节就行，对传送门需要特别处理下~

代码：

#include
#include
#include
#include
using namespace std;
const int maxn=51;
struct node
{int x;int y;int ans;
};
queue q;
bool vis[maxn][maxn];
char map[maxn][maxn];
int gox[maxn][maxn],goy[maxn][maxn],fx[maxn],fy[maxn];
int movex[4]={0,0,-1,1},movey[4]={1,-1,0,0};
int n,m;
int main()
{int T;scanf("%d",&T);while(T--){memset(vis,0,sizeof(vis));memset(gox,0,sizeof(gox));memset(goy,0,sizeof(goy));memset(fx,0,sizeof(fx));memset(fy,0,sizeof(fy));scanf("%d%d",&n,&m);for(int i=0;i<=n+1;i++)map[i][0]=map[i][m+1]='#';for(int i=0;i<=m+1;i++)map[0][i]=map[n+1][i]='#';for(int i=1;i<=n;i++){getchar();for(int j=1;j<=m;j++){scanf("%c",&map[i][j]);if(map[i][j]=='L'){q.push((node){i,j});vis[i][j]=1;}else if(map[i][j]>='a'&&map[i][j]<='z'){if(!fx[map[i][j]-'a']){fx[map[i][j]-'a']=i;fy[map[i][j]-'a']=j;}else{gox[i][j]=fx[map[i][j]-'a'];goy[i][j]=fy[map[i][j]-'a'];gox[fx[map[i][j]-'a']][fy[map[i][j]-'a']]=i;goy[fx[map[i][j]-'a']][fy[map[i][j]-'a']]=j;}}}}int ans=-1;while(!q.empty()){node ita=q.front();q.pop();for(int i=0;i<4;i++){int itx=ita.x+movex[i];int ity=ita.y+movey[i];if(map[itx][ity]>='a'&&map[itx][ity]<='z'){int a=itx;int b=ity;itx=gox[a][b];ity=goy[a][b];}if(vis[itx][ity]||map[itx][ity]=='#')continue;if(map[itx][ity]=='Q'){ans=ita.ans+1;break;}q.push((node){itx,ity,ita.ans+1});vis[itx][ity]=1;}if(ans!=-1){while(!q.empty())q.pop();break;}}printf("%d\n",ans);}return 0;	
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！