大神的探险 之 寻找宝藏-题解（C++代码）

解题思路:
DFS依次尝试每一步的所有走法
注意事项:

参考代码:

#include<iostream>

using namespace std;

int min_time=999;

int n,m;

void dfs(char map[50][50],int flag[50][50],int i,int j,int time)

{

    //printf("dfs(%c,%d,%d,%d)\n",map[i][j],i,j,time);

    if(i+1<n&&map[i+1][j]!='X'&&flag[i+1][j]==0)   //下 

    {

        flag[i+1][j]=1;

        if(map[i+1][j]=='E')

            dfs(map,flag,i+1,j,time+1);

        else if(map[i+1][j]=='T')

            dfs(map,flag,i+1,j,time+2);

        else if(map[i+1][j]=='A')

        {

        flag[i+1][j]=0;

            time++;

            if(time<min_time)

                min_time=time;

            //printf("dfs(%c,%d,%d,%d)\n",map[i+1][j],i+1,j,time);

        }

    }

    if(j+1<m&&map[i][j+1]!='X'&&flag[i][j+1]==0)   //右 

    {

        flag[i][j+1]=1;

        if(map[i][j+1]=='E')

            dfs(map,flag,i,j+1,time+1);

        else if(map[i][j+1]=='T')

            dfs(map,flag,i,j+1,time+2);

        else if(map[i][j+1]=='A')

        {

        flag[i][j+1]=0;

            time++;

            if(time<min_time)

                min_time=time;

            //printf("dfs(%c,%d,%d,%d)\n",map[i][j+1],i,j+1,time);

        }

    }

    if(j-1>=0&&map[i][j-1]!='X'&&flag[i][j-1]==0)  //左 

    {

        flag[i][j-1]=1;

        if(map[i][j-1]=='E')

            dfs(map,flag,i,j-1,time+1);

        else if(map[i][j-1]=='T')

            dfs(map,flag,i,j-1,time+2);

        else if(map[i][j-1]=='A')

        {

        flag[i][j-1]=0;

            time++;

            if(time<min_time)

                min_time=time;

            //printf("dfs(%c,%d,%d,%d)\n",map[i][j-1],i,j-1,time);

        }

    }

    if(i-1>=0&&map[i-1][j]!='X'&&flag[i-1][j]==0)  //上 

    {

        flag[i-1][j]=1;

        if(map[i-1][j]=='E')

            dfs(map,flag,i-1,j,time+1);

        else if(map[i-1][j]=='T')

            dfs(map,flag,i-1,j,time+2);

        else if(map[i-1][j]=='A')

        {

        flag[i-1][j]=0;

            time++;

            if(time<min_time)

                min_time=time;

            //printf("dfs(%c,%d,%d,%d)\n",map[i-1][j],i-1,j,time);

        }

    }

}

int main()

{

    while(cin>>n>>m)

    {

        char map[50][50];

        int flag[50][50]={0};

        int x,y;

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

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

        {

            cin>>map[i][j];

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

            {

                x=i;

                y=j;

            }

        }

        flag[x][y]=1;

        dfs(map,flag,x,y,0);

        if(::min_time!=999)

            cout<<::min_time<<endl;

        else

            cout<<"Game Over!"<<endl;

        ::min_time=999;

    }

    return 0;

}