题解 | #迷宫问题#

/*
dfs 标记走过的路
额外temp记录走过的路
注意初始化和申请内存。
防止二维数组传参导致问题，均设为全局变量。
*/

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

const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};

int **temp;
int tempSize;

int **nums;

void dfs(int m,int n,int x,int y){
    if(x==m-1 && y==n-1){
        for(int i = 0; i < tempSize; i++){
            printf("(%d,%d)\n",temp[i][0],temp[i][1]);
        }
        return;
    }
    for(int i = 0; i < 4; i++){
        int mx = x + dx[i];
        int my = y + dy[i];
        if(mx>=0 && my>=0 && mx<m && my<n && nums[mx][my]==0){
            nums[mx][my] = 1;
            temp[tempSize][0] = mx;
            temp[tempSize++][1] = my;
            dfs(m,n,mx,my);
            nums[mx][my] = 0;
            tempSize--;
        }
    }
}

int main(){
    int m,n;
    scanf("%d %d\n",&m,&n);
    //printf("%d,%d",m,n);
    //原数组
    nums = (int**)malloc(sizeof(int*)*m);
    for(int i = 0; i < m; i++){
        nums[i] = (int*)calloc(n,sizeof(int));
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            scanf("%d",&nums[i][j]);
            //printf("%d ",nums[i][j]);
        }
    }
    //存储经过的点
    temp = (int**)malloc(sizeof(int*)*m*n);
    for(int i = 0; i < m*n; i++){
        temp[i] = (int*)calloc(2,sizeof(int));
    }
    tempSize = 0;
    //初始点入队
    nums[0][0] = 1;
    temp[tempSize][0] = 0;
    temp[tempSize++][1] = 0;
    dfs(m,n,0,0);
    return 0;
}