当前位置: 代码迷 >> 综合 >> HDU 1242 Rescue (DFS)
  详细解决方案

HDU 1242 Rescue (DFS)

热度:88   发布时间:2023-12-05 06:39:18.0
//题意自己看,不会度娘
#include <stdio.h>
#include <math.h>
#include <string.h>
char map[205][205];//地图
int flag[205][205];//标记
int n,m,ok,num;
void DFS(int x,int y,int step)
{if(flag[x][y]||map[x][y]=='#'||step>=num)//剪枝。如果走到墙或者步数不是最少还有这个坐标已经走过return;if(map[x][y]=='r')//表示已经营救成功{ok=1;if(step<num)num=step;return;}if(map[x][y]=='x')//如果是警卫,步数加一step++;flag[x][y]=1;//将flag[x][y]标记为1表示已走DFS(x+1,y,step+1);DFS(x-1,y,step+1);DFS(x,y+1,step+1);DFS(x,y-1,step+1);//四个方向一一走过,可以继续走的话就继续往下走flag[x][y]=0;//如果运行到这里说明四个方向都不行,将flag[x][y]重新标记为未走
} 
int main(int argc, char *argv[])
{
while(~scanf("%d %d%*c",&n,&m))
{int si,sj,i,j;memset(map,'#',sizeof(map));for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%c",&map[i][j]);if(map[i][j]=='a'){si=i;sj=j;}//标记位置}getchar();}
ok=0;
num=100000;
DFS(si,sj,0);
if(ok)
printf("%d\n",num);
else
printf("Poor ANGEL has to stay in the prison all his life.\n");    
}return 0;
}
//Start-ZJ