[C++知识库]杭电1242（C++）dfs版

杭电1242

题目

AC代码

#include<iostream>
#include<cstring>
using namespace std;
int d[4][2]= {{0,1},{0,-1},{1,0},{-1,0}},n,m,T;
char map[205][205];
int vist[205][205];
void dfs(int sx,int sy,int time)
{
    int nx,ny,i;
    if(map[sx][sy]=='r'&&time<T)//成功条件 
    {
        T=time;
        return;
    }
    if(time>=T)
        return;
    for(i=0; i<4; i++)
    {
        nx=sx+d[i][0];
        ny=sy+d[i][1];
        if(nx<0||nx>=n||ny<0||ny>=m||map[nx][ny]=='#'||vist[nx][ny])
            continue;
        vist[nx][ny]=1;
        if(map[sx][sy]=='x')
            dfs(nx,ny,time+2);
        else
            dfs(nx,ny,time+1);
        vist[nx][ny]=0;
    }
}
int main()
{
    int sx,sy,i,j;
    while(cin>>n>>m)
    {
        getchar();
        memset(vist,0,sizeof(vist));
        for(i=0; i<n; i++)
            for(j=0; j<m; j++)
            	cin>>map[i][j];
        for(i=0; i<n; i++)
            for(j=0; j<m; j++)
                if(map[i][j]=='a')
                {
                    sx=i;
                    sy=j;
                    vist[sx][sy]=1;
                    break;
                }
        T=1000000;
        dfs(sx,sy,0);
        if(T==1000000)
            cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
        else
            cout<<T<<endl;
    }
    return 0;
}

解题思路

采用深度优先搜索求解
建立二维地图
建立状态转移数组
根据物体不同进行相应的时间加减
从天使向他的朋友进行搜索
可以采用广度优先搜索求解

出现问题

没有想到天使向朋友搜索