HDU 1242 Rescue (DFS)-蒲公英云

HDU 1242 Rescue (DFS)

清疚 2022-06-08 08:42 253阅读 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