题解 | #迷宫问题#

思路：

1. 确定当前坐标点(x,y)后，接下来的路径为：
2. 向左(x+1,y) 向右(x-1,y) 向上(x,y+1) 向下(x,y-1)
3. 遍历所有的可行路径
4. 当到达终点后，判断最短的路径并记录下来，输出即可

#include <stdio.h>
#include <string.h>

typedef struct
{
    int x;
    int y;
}CoorInfo_t;

static CoorInfo_t g_coor[100] = {0};//记录当前路径
static CoorInfo_t g_min[100] = {0};//记录最短路径
static int m = 0, n = 0;
static int maze[10][10] = {0};
static int minPath = 100;

static void SearchPath(int x, int y, int len)
{
    //printf("(%d.%d)-->[%d]\n", x, y, len);
    g_coor[len].x = x;
    g_coor[len].y = y;
    len++;
    /* 说明找到出口了 */
    if(x == m-1 && y == n-1)
    {
        if(len < minPath)
        {
            minPath = len;
        }
        for(int i = 0; i < minPath; i++)
        {
            g_min[i].x = g_coor[i].x;
            g_min[i].y = g_coor[i].y;
      }
    }
    else
    {
        maze[x][y] = -1;    //已经走过的点，设置为-1
        
        /* 一下四个点为当前点的四种可能 */
        if(maze[x][y+1] == 0 && y+1 < n)
        {
            SearchPath(x, y+1, len);
        }
        if(maze[x][y-1] == 0 && y-1 >= 0)//向下
        {
            SearchPath(x, y-1, len);
        }
        if(maze[x+1][y] == 0 && x+1 < m)//向右
        {
            SearchPath(x+1, y, len);
        }
        if(maze[x-1][y] == 0 && x-1 >= 0)//向左
        {
            SearchPath(x-1, y, len);
        }
        /***************************************/
        
        maze[x][y] = 0;//以此为出发点的路径全部遍历完毕
    }
}

int main()
{
    scanf("%d %d", &m, &n);
    /* 输入迷宫数据 */
    int len = 0;
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &maze[i][j]);
            //printf("%d ", maze[i][j]);
        }
        //printf("\n");
    }
    
    SearchPath(0, 0, len);
    //printf("minPath = [%d]\n", minPath);
    
    for(int i = 0; i < minPath; i++)
    {
        printf("(%d,%d)\n", g_min[i].x, g_min[i].y);
    }
    
    return 0;
}