poj-3984-迷宫问题

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
int map[5][5],record[5][5]={1},min=25,res[5][5];
int walk[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int step,int x,int y){
    int j,l;
    if(x==4&&y==4){
        if(step<min){
            min=step;
            for(j=0;j<5;j++){
                for(l=0;l<5;l++){
                    res[j][l]=record[j][l];
                }
            }
        }
        return;
    }
    int i;
    for(i=0;i<4;i++){
        if(map[y+walk[i][0]][x+walk[i][1]]==0&&record[y+walk[i][0]][x+walk[i][1]]==0&&y+walk[i][0]<5&&y+walk[i][0]>=0&&x+walk[i][1]<5&&x+walk[i][1]>=0){
            record[y+walk[i][0]][x+walk[i][1]]=step;
            dfs(step+1, x+walk[i][1], y+walk[i][0]);
            record[y+walk[i][0]][x+walk[i][1]]=0;
        }
    }
    return;
}
int main(){
    int i,j,k;
    for(i=0;i<5;i++){
        for(j=0;j<5;j++){
            scanf("%d",&map[i][j]);
        }
    }
    dfs(1, 0, 0);
    for(i=1;i<min;i++){
        for(j=0;j<5;j++){
            for(k=0;k<5;k++){
                if(res[j][k]==i){
                    printf("(%d, %d)n",j,k);
                }
            }
        }
    }
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <time.h>
struct queue{
    int x;
    int y;
}in[100];
int rec[100];
void print(int tail){
    if(tail==0){
        printf("(0, 0)n");
        return;
    }
    else{
        print(rec[tail]);
        printf("(%d, %d)n",in[tail].y,in[tail].x);
        return;
    }
}
int main() {
    int map[10][10],find=0;
    int i,j,head=0,tail=0;
    int walk[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
    for(i=0;i<5;i++){
        for(j=0;j<5;j++){
            scanf("%d",&map[i][j]);
        }
    }
    in[0].x=0;
    in[0].y=0;
    tail++;
    rec[1]=0;
    while(head<=tail){
        for(i=0;i<4;i++){
            int tempy=in[head].y+walk[i][0];
            int tempx=in[head].x+walk[i][1];
            if(tempy>4||tempx>4||tempy<0||tempx<0){
                continue;
            }
            if(map[tempy][tempx]==0){
                in[tail].x=tempx;
                in[tail].y=tempy;
                rec[tail]=head;
                map[tempy][tempx]=1;
                tail++;
            }
            if(tempy==tempx&&tempy==4){
                find=1;
                break;
            }
        }
        if(find==1){
            break;
        }
        head++;
    }
    print(tail-1);
    return 0;
}

题目是中文的,不解释了,照着啊哈算法的样子就能做出来.
广搜输出有技巧,只要知道了子节点只有一个父亲而父节点有多个儿子这个观念,就能逆向输出路径了,但是这个题深搜明显思路简单😂!!!!!