蓝桥杯2015年第六届真题-穿越雷区 （C语言代码）

解题思路:

  DFS 核心代码，根据题意添加操作。

void DFS( 状态参数 ) {

    if ( 目的状态 ) {

        目的操作

        return;

    }

    for ( 搜索方式(移动) )

    {

        if ( 合法状态 ) {

            操作

            标记

            DFS（ 更新状态参数 ）

            回溯 ( 还原标记 )

        }

    }

}

注意事项:

参考代码:

#include <iostream>

using namespace std;

char a[100][100];

int x1,x2,y1,y2,n;

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

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

int vis[100][100];

int k=999999;

void dfs(int x,int y,int m)

{

    if(a[x][y]=='B')

    {

        if(k>m) k=m; 

        return ;

    }

}

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

{

    if(a[x][y]!=a[xx[i]+x][yy[i]+y] && xx[i]+x>0 && xx[i]+x<=n && yy[i]+y>0 && yy[i]+y<=n &&     !vis[xx[i]+x][yy[i]+y])

    {

        vis[xx[i]+x][yy[i]+y]=1;

        dfs(xx[i]+x,yy[i]+y,m+1);

        vis[xx[i]+x][yy[i]+y]=0;

     }

}

int main()

{

cin>>n;

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

{

    for(int j=1;j<=n;j++)

    {

        cin>>a[i][j];

        if(a[i][j]=='A'){x1=i;y1=j;}

        if(a[i][j]=='B'){x2=i;y2=j;}

    }

}

    dfs(x1,y1,0);

    cout<<k;

    return 0;

}