题解 | #迷宫问题#

DFS

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

typedef struct pointinfo
{
    int set;
    int row;
    int col;
    int value;
    int prior;
} pointinfo;

void DFS(pointinfo *maze, int m, int n, int pos);
int main()
{
    int m, n;
 while((scanf("%d %d", &m, &n))!=EOF) {
        pointinfo maze[m * n];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &maze[n * i + j].value);
            maze[n * i + j].row = i, maze[n * i + j].col = j;
            maze[n * i + j].prior = -1, maze[n * i + j].set = 0;
        }
maze[0].set =1;
    DFS(maze,m,n,0);
    int point[100][2];
    int step=0;
    int now=m*n-1;
    while(now !=-1){
     point[step][0] = maze[now].row;
       point[step][1] = maze[now].col;  
         step++;
    now = maze[now].prior;    
    }
    for(int i=step-1;i>=0;i--)
  printf("(%d,%d)\n",point[i][0],point[i][1]);
    
    
 }  
 
    return 0;
}






void DFS(pointinfo *maze, int m, int n, int pos)
{
    int isnotsihutong = 1;
    while (maze[n * m].prior == -1 || isnotsihutong == 1)
    {
        isnotsihutong = 0;
        if (pos - n >= 0 && maze[pos - n].value == 0 && maze[pos - n].set == 0)
        {
            maze[pos - n].set = 1;
            maze[pos - n].prior = pos;
            isnotsihutong = 1;
            DFS(maze, m, n, pos - n);
        }

        if (pos + n < m * n && maze[pos + n].value == 0 && maze[pos + n].set == 0)
        {
            maze[pos + n].set = 1;
            maze[pos + n].prior = pos;
            isnotsihutong = 1;
            DFS(maze, m, n, pos + n);
        }

        if (pos % n != 0 && maze[pos - 1].value == 0 && maze[pos - 1].set == 0)
        {
            maze[pos - 1].set = 1;
            maze[pos - 1].prior = pos;
            isnotsihutong = 1;
            DFS(maze, m, n, pos - 1);
        }

        if (pos % n != n - 1 && maze[pos + 1].value == 0 && maze[pos + 1].set == 0)
        {
            maze[pos + 1].set = 1;
            maze[pos + 1].prior = pos;
            isnotsihutong = 1;
            DFS(maze, m, n, pos + 1);
        }
    }
}