走出迷宮
給予一個二維整數陣列,以1表示牆壁,0表示通道,構成一個迷宮。你可以用直角方向(上u,下d,左l,右r)在迷宮中移動,想辦法從入口走到出口。入口座標固定為(0,1),出口座標固定為(N-2, M-1)如下所示:
N為5
M為7
1 0 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 0 1 1 1
1 0 1 0 0 0 0
1 1 1 1 1 1 1
範例輸入
5
7
1 0 1 1 1 1 1
1 0 0 0 0 0 1
1 0 1 0 1 1 1
1 0 1 0 0 0 0
1 1 1 1 1 1 1
範例輸出
drrddrrr
#include <stdio.h>
void f(char a1[],int b1[][9],int M,int N,int x,int y,int *path){
int i=0;
b1[x][y]=2;
//printf("%d,%d\n",x,y);
if(x==M-2&&y==N-1){
for(i=0;i<(*path);i++)
printf("%c",a1[i]);
}
else{
//上
int nxt_x,nxt_y;
nxt_x=x-1;
nxt_y=y;
if(nxt_x>=0){
if(b1[nxt_x][nxt_y]==0){
a1[(*path)++]='u';
f(a1,b1,M,N,nxt_x,nxt_y,path);
}
}
//左
nxt_x=x;
nxt_y=y-1;
if(nxt_y>=0){
if(b1[nxt_x][nxt_y]==0){
a1[(*path)++]='l';
f(a1,b1,M,N,nxt_x,nxt_y,path);
}
}
//下
nxt_x=x+1;
nxt_y=y;
if(nxt_x<M){
if(b1[nxt_x][nxt_y]==0){
a1[(*path)++]='d';
f(a1,b1,M,N,nxt_x,nxt_y,path);
}
}
//右
nxt_x=x;
nxt_y=y+1;
if(nxt_y<N){
if(b1[nxt_x][nxt_y]==0){
a1[(*path)++]='r';
f(a1,b1,M,N,nxt_x,nxt_y,path);
}
}
}
(*path)--;
}
int main(){
int b1[9][9],i,j,M,N,path=0;
char a1[99];
scanf("%d%d",&M,&N);
for(i=0;i<M;i++){
for(j=0;j<N;j++){
scanf("%d",&b1[i][j]);
}
}
f(a1,b1,M,N,0,1,&path);
return 0;
}