题目：

定义一个二维数组： int maze[5][5] = {    0, 1, 0, 0, 0,    0, 1, 0, 1, 0,    0, 0, 0, 0, 0,    0, 1, 1, 1, 0,    0, 0, 0, 1, 0,};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

input:

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

output:

左上角到右下角的最短路径，格式如样例所示。

sample input:

0 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0

sample output:

(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4)

AC code：

#include
     
      #include
      
       #include
       
        using namespace std;stack
        
          s1,s2;int maze[5][5];bool dfs(int x,int y){    if(x==4&&y==4)         //dfs递归的出口    {        s1.push(x);             //记录迷宫出口的坐标，返回true给上一层的if判断；        s2.push(y);        return true;    }    if(x>=0&&x<=4&&y>=0&&y<=4)    {        if(maze[x][y]==0)        {            maze[x][y]=1;            if(dfs(x,y+1)||dfs(x+1,y)||dfs(x-1,y)||dfs(x,y-1))   //这个判断条件对唯一解才能有效的判断，若解不唯一，应当重新设定dfs函数的循环跳出条件；            {                s1.push(x);     //若最后的结果可行，从出口往入口进栈，然后不断的返回true给上一层if调用，不断的进栈记录路径；                s2.push(y);                return true;             }            else            {                maze[x][y]=0;        //如果走不通，则返回false，这样就不断的重新恢复迷宫原来的都1与0；                return false;            }        }        else        {            return false;        }    }    else    {        return false;    }}void print(){    while(s1.empty()!=true)    {        printf("(%d, %d)\n",s1.top(),s2.top());        s1.pop();        s2.pop();    }}int main(){    int temp=0;    while(scanf("%d",&temp)!=EOF)    {        for(int i=0;i<5;i++)        {            for(int j=0;j<5;j++)            {                if(i==0&&j==0)  {maze[i][j]=temp;continue;}                else scanf("%d",&maze[i][j]);            }        }        dfs(0,0);        print();    }    return 0;}
        
       
      
     

TIP：

解题思路：深度优先搜索+递归

难度：入门级经典