题目链接

 

水题，bfs

代码

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<queue>

using namespace std;

int n,m,success;

int stx,sty,ex,ey;

char map[210][210];

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

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

struct node

{

int x,y,g,cnt;

};

queue<node> q;

void bfs()

{

node s,e;

while(q.size())

q.pop();

s.x=stx; s.y=sty; s.cnt=0; s.g=0;

q.push(s);

while(q.size())

{

s=q.front();

q.pop();

if(s.x==ex&&s.y==ey)

{

success=1;

printf("%d\n",s.cnt);

return ;

}

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

{

e.x=s.x+dx[i]; e.y=s.y+dy[i];

if(e.x>=0&&e.x<n&&e.y>=0&&e.y<m&&map[e.x][e.y]!='#')

{

if(s.g==0)

{

if(map[e.x][e.y]=='x')

{

e.g=1;

e.cnt=s.cnt+1;

q.push(e);

map[e.x][e.y]='#';

}

else

{

e.g=0;

e.cnt=s.cnt+1;

q.push(e);

map[e.x][e.y]='#';

}

}

else

{

s.g=s.g-1;

s.cnt=s.cnt+1;

q.push(s);

}

}

}

}

}

int main(void)

{

int i,j;

while(scanf("%d%d",&n,&m)==2)

{

getchar();

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

{

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

{

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

if(map[i][j]=='r')

{

stx=i; sty=j;

}

else if(map[i][j]=='a')

{

ex=i; ey=j;

}

}

getchar();

}

success=0;

bfs();

if(!success)

printf("Poor ANGEL has to stay in the prison all his life.\n");

}

return 0;

}