2018年长沙理工大学第十三届程序设计竞赛

点击打开链接

#include <bits/stdc++.h>

using namespace std;

const int N=5e2+66;

int visit[N][N][2];

char mp[N][N];

int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

struct node{

int x,y;

int flag,step;

};

int n,m;

int dfs(int x,int y)

{

int tx,ty;

memset(visit,0,sizeof(visit));

queue<node> que;

node tmp; tmp.x=x; tmp.y=y; tmp.flag=0; tmp.step=0;

visit[x][y][tmp.flag]=1; que.push(tmp);

while(!que.empty())

{

node q=que.front();

que.pop();

if(mp[q.x][q.y]== 'E')return q.step;

for(int i=0;i<4;i++)

{

tx=q.x+dir[i][0];

ty=q.y+dir[i][1];

if(tx>=0&&tx<n&&ty>=0&&ty<m&&mp[tx][ty]!='#')

{

node tp;

if(mp[tx][ty]=='K')

tp.flag=1;

else tp.flag=q.flag;

if(visit[tx][ty][tp.flag])continue;

visit[tx][ty][tp.flag]=1;

if(mp[tx][ty]== 'E'&&!visit[tx][ty][1])

continue;

tp.x=tx;

tp.y=ty;

tp.step=q.step + 1;

que.push(tp);

}

}

}

return -1;

}

int main()

{

int t;

int i,j;

cin>>t;

while(t--)

{

int tx,ty,ans;

cin>>n>>m;

getchar();

for(i=0;i<n;i++)

for(j=0;j<m;j++)

{

scanf("%c",&mp[i][j]);

if(mp[i][j]=='P')

{

tx=i; ty=j;

}

if(i!=n-1&&j==m-1)getchar();

}

ans=dfs(tx,ty);

if(ans==-1)

printf("No solution\n");

else printf("%d\n",ans);      

}

return 0;

}