迷宫（C语言）
迷宫的入口为左上角的黄色方格，出口为右下角的黄色方格。在迷宫中，只能从一个方格走到相邻的上、下、左、右四个方向之一。找到一条从起点到终点的迷宫路径，并将路径输出。如果从起点到终点没有路径，则输出NO PASS!
注：所有迷宫的起点为左上角，终点为右下角。
【输入形式】依次输入n行由0和1构成的字符串，每行字符串长度相同，输入空串结束，其中1表示围墙，0表示可行路径。
【输出形式】如果起点到终点有路，则依次输出由L、R、D、U组成的路径字符串；否则输出NO PASS!。
【样例输入】
0111111
0011101
1001101
0011001
1000111
1110000
【样例输出】
DRDDDRRDRRR 本帖最后由 jhq999 于 2022-5-28 22:30 编辑
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={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.x=i;
a.y=j;
if('1'==getchar())a.ispass=1;
else a.ispass=0;
}
getchar();
}
a.ispass=0;
a.ispass=0;
fun((ptini*)a,0,(ptini*)a,&a,pathstr,&len);
pathstr=0;
printf("%s",pathstr+len);
free(pathstr);
return 0;
} 本帖最后由 蔚蓝水晶 于 2022-6-18 16:12 编辑
#include <stdio.h>
#define W 100 //迷宫的宽
char De={'U','D','L','R'}; //用来输出路径
int deM(int a[],int road[],int count,int h,int w,int choice,int x,int y); //检测函数，用来指明方向
int mm(int a[],int road[],int count,int h,int w,int choice,int x,int y); //deM的过渡函数，主要用来生成完整路径
int mm(int a[],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=De;
return 1;
}
else
return 0;
}
int deM(int a[],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,road={0};
for(i=0;i<h;i++){
printf("请输入第%d行迷宫：",i+1);
for(j=0;j<w;j++){
scanf("%d",&M);
getchar();
}
}
if(deM(M,road,0,h-1,w-1,-1,0,0)){
for(i=0;i<h*w;i++)
printf("%c",road);
}
else
printf("No pass!");
}
页:
[1]