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

解题思路:
假设初始状态是雷区中所有辐射点未曾被访问，则深度优先搜索可访问从起点可达的其中某个辐射点，从该点出发，占用该点，然后从四个方向找到下一步的位置，依次从未被占用且与上一步相异的邻接点出发深度优先遍历雷区，直至区域内所有和占用点有路径相通且前后相异的辐射点都被访问到，才可解除占用；若此时雷区中尚有从起点可达的辐射点未被访问，则继续找到起始占用点，重复上述过程，直至雷区中所有从起点出发，按既定规则可达的辐射点都被访问到，在遍历过程中若能到达终点，且有更短路径，则记录其步数并返回。

注意事项:
若下一步超出范围或不符合坦克前进的规则，可继续搜索其它方向，且不必判断是否需要继续做深度优先搜索。

参考代码:

#include<stdio.h>
#define MN 101
char s[MN][MN];
int occupy[MN][MN];
int N,startX,startY,endX,endY;
int MIN1=0x7fffffff;
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int,int,int);
int main(){
    int i,j;
    scanf("%d",&N);
    getchar();
    for(i=0;i<N;i++)
        for(j=0;j<N;j++){
            scanf("%c",&s[i][j]);        //输入雷区矩阵
            getchar();
            if(s[i][j]=='A'){            //若为起点
                startX=i;                //记录起点行号
                startY=j;                //记录起点列号
            }else if(s[i][j]=='B'){      //若为终点
                endX=i;                  //记录终点行号
                endY=j;                  //记录终点列号
            }
            occupy[i][j]=0;              //初始化访问数组
        }
    occupy[startX][startY]=1;            //起点被占用
    dfs(startX,startY,1);                //从起点开始做深度优先搜索
    if(MIN1==0x7fffffff) MIN1=-1;        //未搜索到可达终点的路径
    printf("%d\n",MIN1);
    return 0;
}
void dfs(int x,int y,int step){
    int i,tx,ty;
    for(i=0;i<4;i++){                    //东南西北四个方向
        tx=x+next[i][0];                 //下一步的行号
        ty=y+next[i][1];                 //下一步的列号
        if(tx<0||tx>=N||ty<0||ty>=N)     //下一步超出范围
            continue;                    //继续搜索其它方向
        if(tx==endX&&ty==endY){          //到达终点
            if(step<MIN1) MIN1=step;     //若有更短路径记录其步数
            return;                      //搜索到最深，返回
        }
        if(!occupy[tx][ty]&&s[tx][ty]!=s[x][y]){//若下一步未被占用且与这一步相异
                occupy[tx][ty]=1;        //占用下一步
                dfs(tx,ty,step+1);       //从下一步开始做深度优先搜索
                occupy[tx][ty]=0;        //解除占用
        }
    }
}