题解 | #迷宫问题#

#include <stdio.h>
int maze[10][10];
int hang,lie;
int path[1000][2] = {0};
int max_path[1000][2] = {0};
int max_len = 0;;

void DFS(int x,int y,int index)
{
    if(x == hang-1 && y == lie-1)
    {
        path[index][0] = x;
        path[index][1] = y;
        index++;
        if(index>max_len)
        {
            max_len = index;
            for(int i = 0;i<index;i++)
            {
                max_path[i][0] = path[i][0];
                max_path[i][1] = path[i][1];
            }
        }
        return;
    }
    else if(maze[x][y] == 0)
    {
        path[index][0] = x;
        path[index][1] = y;

        maze[x][y] = 1;
        index++;
        if(x+1<hang && maze[x+1][y]==0)
        {
            DFS(x+1, y, index);
        }
        if(x-1>=0 && maze[x-1][y]==0)
        {
            DFS(x-1, y, index);
        }
        if(y+1<lie && maze[x][y+1]==0)
        {
            DFS(x, y+1, index);
        }
        if(y-1>=0 && maze[x][y-1]==0)
        {
            DFS(x, y-1, index);
        }
        maze[x][y] = 0;
    }else {
        return;
    }

}

int main() {
    while (~scanf("%d %d",&hang,&lie)) {
        for(int i = 0;i<hang;i++)
        {
            for(int j = 0;j<lie;j++)
            {
                scanf("%d",&maze[i][j]);
            }
        }   
    }
    DFS(0, 0, 0);

    for(int i = 0;i<max_len;i++)
    {
        printf("(%d,%d)\n",max_path[i][0],max_path[i][1]);
    }

}