题解 | #迷宫问题#

#include <stdio.h>
int min=105;
int n,m;
int p[15][15],a[105][5],b[105][5],mat[15][15];
void dps(int x,int y,int step){
    if(x==n-1&&y==m-1){
        if(min>step){
            min=step;
            for(int i=0;i<=min;i++){
                b[i][0]=a[i][0];
                b[i][1]=a[i][1];
            }            
        }
        return;
    }
    if(x-1>=0){
        if(mat[x-1][y]==0&&p[x-1][y]==0){
            mat[x-1][y]=1;
            a[step+1][0]=x-1;
            a[step+1][1]=y;
            dps(x-1,y,step+1);
            mat[x-1][y]=0;
        }        
    }
    if(x+1<n){
        if(mat[x+1][y]==0&&p[x+1][y]==0){
            mat[x+1][y]=1;
            a[step+1][0]=x+1;
            a[step+1][1]=y;
            dps(x+1,y,step+1);
            mat[x+1][y]=0;
        }      
    }
    if(y-1>=0){
        if(mat[x][y-1]==0&&p[x][y-1]==0){
            mat[x][y-1]=1;
            a[step+1][0]=x;
            a[step+1][1]=y-1;
            dps(x,y-1,step+1);
            mat[x][y-1]=0;
        }        
    }
    if(y+1<m){
        if(mat[x][y+1]==0&&p[x][y+1]==0){
            mat[x][y+1]=1;
            a[step+1][0]=x;
            a[step+1][1]=y+1;
            dps(x,y+1,step+1);
            mat[x][y+1]=0;
        }
    }
}

int main() {
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            scanf("%d",&p[i][j]);
            mat[i][j]=0;
        }
    a[0][0]=0;a[0][1]=0;
    dps(0,0,0);   
    for(int i=0;i<=min;i++)
        printf("(%d,%d)\n",b[i][0],b[i][1]);    
    return 0;
}