题解 | #迷宫问题#

#include <stdio.h>
int tace[100][2];  
int realtace[100][2];
int minstep = 100;
int maze[10][10];
int tage[10][10] = { 0 };
int p, q;
int n, m;


void dfs(int x, int y, int maze[10][10], int step)
{
    tace[step][0] = x;
    tace[step][1] = y;
    if (x == q && y == p)
    {
	  // 最短路径
        if (step < minstep)
        {
            minstep = step;
            //printf("%d   ", step);
            for (int i = 0; i <= minstep; i++)
            {
                realtace[i][0] = tace[i][0];
                realtace[i][1] = tace[i][1];
                //printf("%d %d\n", realtace[i][0], realtace[i][1]);
            }
        }
        return;
    }
    if (x < 0 || y < 0 || y > p || x > q)
        return;
    // 右边
    //printf("%d %d\n", x, y);
    
    if (maze[x ][y +1] == 0 && tage[x][y + 1] == 0)
    {
        tage[x][y + 1] = 1;
        dfs(x, y+1, maze, step + 1);
    }
    // 下边
    if (maze[x + 1][y] == 0 && tage[x + 1][y] == 0)
    {
        tage[x + 1][y] = 1;
        dfs(x + 1, y , maze, step + 1);
    }
    // 左边
     if (maze[x][y -1] == 0 && tage[x][y -1] == 0)
    {
        tage[x][y - 1] = 1;
        dfs(x, y -1, maze, step + 1);
    }
    // 上边
    if (maze[x -1][y] == 0 && tage[x - 1][y] == 0)
    {
        tage[x - 1][y] = 1;
        dfs(x - 1, y, maze, step + 1);
    }
    return;
}


int main() {

    scanf("%d%d", &n, &m);

    p = m - 1;
    q = n - 1;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &maze[i][j]);
    //printf("%d  %d", p, q);
    dfs(0, 0, maze, 0);
  	tage[0][0] = 1;
    for (int i = 0; i <= minstep; i++)
    {
        printf("(%d,%d)\n", realtace[i][0], realtace[i][1]);
    }
    return 0;
}