迷宫（C语言）

柠檬Ccc

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



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

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

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

jhq999

typedef struct POINTINI
{
        int x;
        int y;
        int ispass;
}ptini,*pptini;
int fun(ptini* pt, int fx/*来的方向（上下左右）*/,ptini* start,ptini* end,char* patnstr,int* strlen)
{
        int row=end->x-start->x,col=end->y-start->y;
        row=(row<0?-1*row:row)+1,col=(col<0?-1*col:col)+1;
        if (pt->x==end->x&&pt->y==end->y)
        {
                return 1;
        }
        if (pt->ispass)return 0;
        if (fx!=3&&(pt->y+1<col)&&fun(pt+1,2,start,end,patnstr,strlen))
        {
                patnstr[--(*strlen)]='R';
        
                

        }
        else if(fx!=1&&(pt->x+1<row)&&fun(pt+col,0,start,end,patnstr,strlen))
        {
                patnstr[--(*strlen)]='D';
        
                
        }
        else if(fx!=2&&(pt->y-1>=0)&&fun(pt-1,3,start,end,patnstr,strlen))
        {
                patnstr[--(*strlen)]='L';
        
                
                
        }
        else if(fx!=0&&(pt->x-1>=0)&&fun(pt-col,1,start,end,patnstr,strlen))
        {
                patnstr[--(*strlen)]='U';
        }
        else
        {
                pt->ispass=1;
                return 0;
        }
        pt->ispass=1;
        return 1;
}
int main()
{

        ptini a[6][7]={0};
        int len=6*7+1;
        char * pathstr=(char*)malloc(6*7+1);
        for (int i = 0; i < 6; i++)
        {
                for (int j = 0; j < 7; j++)
                {
                        a[i][j].x=i;
                        a[i][j].y=j;
                        if('1'==getchar())a[i][j].ispass=1;
                        else a[i][j].ispass=0;
                }
                getchar();
        }
        a[0][0].ispass=0;
        a[5][6].ispass=0;
        fun((ptini*)a,0,(ptini*)a,&a[5][6],pathstr,&len);
        pathstr[42]=0;
        printf("%s",pathstr+len);
        free(pathstr);
        return 0;

}

蔚蓝水晶

#include <stdio.h>
#define W 100           //迷宫的宽

char De[4]={'U','D','L','R'};           //用来输出路径

int deM(int a[][W],int road[],int count,int h,int w,int choice,int x,int y);         //检测函数，用来指明方向
int mm(int a[][W],int road[],int count,int h,int w,int choice,int x,int y);      //deM的过渡函数，主要用来生成完整路径

int mm(int a[][W],int road[],int count,int h,int w,int choice,int x,int y){
    int n=count+1;

    if(deM(a,road,n,h,w,choice,x,y)){
        road[count]=De[choice];
        return 1;
    }

    else
        return 0;

}


int deM(int a[][W],int road[],int count,int h,int w,int choice,int x,int y){

    if(h==y&&w==x)
        return 1;
    
    else{

        if(y!=0&&choice!=1){
            if(*(*(a+y-1)+x)==0){
                if(mm(a,road,count,h,w,0,x,y-1))
                    return 1;
            }
        }

        if(y!=h&&choice!=0){
            if(*(*(a+y+1)+x)==0){
                if(mm(a,road,count,h,w,1,x,y+1))
                    return 1;
            }
        }

        if(x!=0&&choice!=3){
            if(*(*(a+y)+x-1)==0){
                if(mm(a,road,count,h,w,2,x-1,y))
                    return 1;
            }
        }

        if(x!=w&&choice!=2){
            if(*(*(a+y)+x+1)==0){
                if(mm(a,road,count,h,w,3,x+1,y))
                    return 1;
            }
        }

        return 0;

    }



}


int main(void){
    int i,j,h,w;

    printf("请输入迷宫的规模：");
    scanf("%d %d",&h,&w);

    getchar();

    int M[h][W],road[h*w+1]={0};

    for(i=0;i<h;i++){
        printf("请输入第%d行迷宫：",i+1);
        for(j=0;j<w;j++){
            scanf("%d",&M[i][j]);
            getchar();
        }

    }

    if(deM(M,road,0,h-1,w-1,-1,0,0)){
        for(i=0;i<h*w;i++)
            printf("%c",road[i]);
    }
    else
        printf("No pass!");
}