迷宫（C语言）

柠檬Ccc

迷宫的入口为左上角的黄色方格，出口为右下角的黄色方格。在迷宫中，只能从一个方格走到相邻的上、下、左、右四个方向之一。



找到一条从起点到终点的迷宫路径，并将路径输出。如果从起点到终点没有路径，则输出NO PASS!

注：所有迷宫的起点为左上角，终点为右下角。

【输入形式】依次输入n行由0和1构成的字符串，每行字符串长度相同，输入空串结束，其中1表示围墙，0表示可行路径。
【输出形式】如果起点到终点有路，则依次输出由L、R、D、U组成的路径字符串；否则输出NO PASS!。
【样例输入】
0111111
0011101
1001101
0011001
1000111
1110000
【样例输出】
DRDDDRRDRRR

jhq999

1. typedef struct POINTINI
   
2. {
   
3.         int x;
   
4.         int y;
   
5.         int ispass;
   
6. }ptini,*pptini;
   
7. int fun(ptini* pt, int fx/*来的方向（上下左右）*/,ptini* start,ptini* end,char* patnstr,int* strlen)
   
8. {
   
9.         int row=end->x-start->x,col=end->y-start->y;
   
10.         row=(row<0?-1*row:row)+1,col=(col<0?-1*col:col)+1;
    
11.         if (pt->x==end->x&&pt->y==end->y)
    
12.         {
    
13.                 return 1;
    
14.         }
    
15.         if (pt->ispass)return 0;
    
16.         if (fx!=3&&(pt->y+1<col)&&fun(pt+1,2,start,end,patnstr,strlen))
    
17.         {
    
18.                 patnstr[--(*strlen)]='R';
    
19.        
    
20.                
    
21. 
    
22.         }
    
23.         else if(fx!=1&&(pt->x+1<row)&&fun(pt+col,0,start,end,patnstr,strlen))
    
24.         {
    
25.                 patnstr[--(*strlen)]='D';
    
26.        
    
27.                
    
28.         }
    
29.         else if(fx!=2&&(pt->y-1>=0)&&fun(pt-1,3,start,end,patnstr,strlen))
    
30.         {
    
31.                 patnstr[--(*strlen)]='L';
    
32.        
    
33.                
    
34.                
    
35.         }
    
36.         else if(fx!=0&&(pt->x-1>=0)&&fun(pt-col,1,start,end,patnstr,strlen))
    
37.         {
    
38.                 patnstr[--(*strlen)]='U';
    
39.         }
    
40.         else
    
41.         {
    
42.                 pt->ispass=1;
    
43.                 return 0;
    
44.         }
    
45.         pt->ispass=1;
    
46.         return 1;
    
47. }
    
48. int main()
    
49. {
    
50. 
    
51.         ptini a[6][7]={0};
    
52.         int len=6*7+1;
    
53.         char * pathstr=(char*)malloc(6*7+1);
    
54.         for (int i = 0; i < 6; i++)
    
55.         {
    
56.                 for (int j = 0; j < 7; j++)
    
57.                 {
    
58.                         a[i][j].x=i;
    
59.                         a[i][j].y=j;
    
60.                         if('1'==getchar())a[i][j].ispass=1;
    
61.                         else a[i][j].ispass=0;
    
62.                 }
    
63.                 getchar();
    
64.         }
    
65.         a[0][0].ispass=0;
    
66.         a[5][6].ispass=0;
    
67.         fun((ptini*)a,0,(ptini*)a,&a[5][6],pathstr,&len);
    
68.         pathstr[42]=0;
    
69.         printf("%s",pathstr+len);
    
70.         free(pathstr);
    
71.         return 0;
    
72. 
    
73. }

复制代码

蔚蓝水晶

1. #include <stdio.h>
   
2. #define W 100           //迷宫的宽
   
3. 
   
4. char De[4]={'U','D','L','R'};           //用来输出路径
   
5. 
   
6. int deM(int a[][W],int road[],int count,int h,int w,int choice,int x,int y);         //检测函数，用来指明方向
   
7. int mm(int a[][W],int road[],int count,int h,int w,int choice,int x,int y);      //deM的过渡函数，主要用来生成完整路径
   
8. 
   
9. int mm(int a[][W],int road[],int count,int h,int w,int choice,int x,int y){
   
10.     int n=count+1;
    
11. 
    
12.     if(deM(a,road,n,h,w,choice,x,y)){
    
13.         road[count]=De[choice];
    
14.         return 1;
    
15.     }
    
16. 
    
17.     else
    
18.         return 0;
    
19. 
    
20. }
    
21. 
    
22. 
    
23. int deM(int a[][W],int road[],int count,int h,int w,int choice,int x,int y){
    
24. 
    
25.     if(h==y&&w==x)
    
26.         return 1;
    
27.    
    
28.     else{
    
29. 
    
30.         if(y!=0&&choice!=1){
    
31.             if(*(*(a+y-1)+x)==0){
    
32.                 if(mm(a,road,count,h,w,0,x,y-1))
    
33.                     return 1;
    
34.             }
    
35.         }
    
36. 
    
37.         if(y!=h&&choice!=0){
    
38.             if(*(*(a+y+1)+x)==0){
    
39.                 if(mm(a,road,count,h,w,1,x,y+1))
    
40.                     return 1;
    
41.             }
    
42.         }
    
43. 
    
44.         if(x!=0&&choice!=3){
    
45.             if(*(*(a+y)+x-1)==0){
    
46.                 if(mm(a,road,count,h,w,2,x-1,y))
    
47.                     return 1;
    
48.             }
    
49.         }
    
50. 
    
51.         if(x!=w&&choice!=2){
    
52.             if(*(*(a+y)+x+1)==0){
    
53.                 if(mm(a,road,count,h,w,3,x+1,y))
    
54.                     return 1;
    
55.             }
    
56.         }
    
57. 
    
58.         return 0;
    
59. 
    
60.     }
    
61. 
    
62. 
    
63. 
    
64. }
    
65. 
    
66. 
    
67. int main(void){
    
68.     int i,j,h,w;
    
69. 
    
70.     printf("请输入迷宫的规模：");
    
71.     scanf("%d %d",&h,&w);
    
72. 
    
73.     getchar();
    
74. 
    
75.     int M[h][W],road[h*w+1]={0};
    
76. 
    
77.     for(i=0;i<h;i++){
    
78.         printf("请输入第%d行迷宫：",i+1);
    
79.         for(j=0;j<w;j++){
    
80.             scanf("%d",&M[i][j]);
    
81.             getchar();
    
82.         }
    
83. 
    
84.     }
    
85. 
    
86.     if(deM(M,road,0,h-1,w-1,-1,0,0)){
    
87.         for(i=0;i<h*w;i++)
    
88.             printf("%c",road[i]);
    
89.     }
    
90.     else
    
91.         printf("No pass!");
    
92. }

复制代码