迷宫求解。。。
输入地迷宫：
8 10
1 1 1 1 1 1 1 1
1 0 1 1 0 1 0 1
1 0 1 0 0 1 0 1
1 1 0 3 1 0 1 1
1 0 0 1 0 0 4 1
1 0 0 0 0 1 1 1
1 0 1 0 0 1 0 1
1 0 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1
- C/C++ code
#include "stdio.h"#include "stdlib.h"typedef struct stack{ int serial;//序号，可有可无，为了方便就有吧 char x; char y; char dir;//方向，0123代表左上右下 struct stack *prev;//上一个 struct stack *next;//下一个}Sta,*pSta;int num;//当前栈数pSta head, temp ,tail;int main(){ int **mode1,**mode2; int x,y; int i,j,z; int m1,n1; int m,n; num=0; scanf("%d%d",&x,&y); mode1=(int **)malloc(y*sizeof(int *)); mode2=(int **)malloc(y*sizeof(int *)); for(i=0;i<y;i++) { mode1[i]=(int *)malloc(x*sizeof(int)); mode2[i]=(int *)malloc(x*sizeof(int)); } for(i=0;i<y;i++) for(j=0;j<x;j++) { scanf("%d",&mode1[i][j]); if(mode1[i][j]==3) { m=i; n=j; } mode2[i][j]=0; } temp=(pSta)malloc(sizeof(Sta)); temp->next=NULL; head=tail=temp; temp=(pSta)malloc(sizeof(Sta)); temp->x=m; temp->y=n; temp->dir=4; temp->serial=++num; tail->next=temp; temp->prev=tail; tail=temp; temp->next=(pSta)1; for(z=0;z<4;z++) { if( z==0 && ( temp->prev==NULL || temp->prev->dir!=2) )//左边（上一个不能是右边） { m = temp->x;n = temp->y+1;//左边一个点的坐标 if(m>=0 && m<=y && n>=0 && n<=x&& mode2[m][n]==0)//必须是有效点，下同 { if(mode1[m][n]==0)//如果是0，入栈，以下同 { temp->dir = z;//记录最后一次探路方向 temp->next = (pSta)malloc(sizeof(Sta));//栈的新成员 temp->next->prev = temp; temp = temp->next;//temp指向新成员 temp->x = m; temp->y = n; temp->dir = 0;//新成员要从0路劲开始探路 temp->serial = ++num;//新序号 temp->next = (pSta)1; z = -1;//i重置 mode2[m][n]=1; } else if(mode1[m][n]==4)//4结束 { m1=m; n1=n; temp->next = NULL; } } } else if( z==1 && ( temp->prev==NULL || temp->prev->dir!=3) ) { m = temp->x-1;n = temp->y; if(m>=0 && m<=y && n>=0 && n<=x&& mode2[m][n]==0) { if(mode1[m][n]==0 ) { temp->dir = z; temp->next = (pSta)malloc(sizeof(Sta)); temp->next->prev = temp; temp = temp->next; temp->x = m; temp->y = n; temp->dir = 0; temp->serial = ++num; temp->next = (pSta)1; z = -1; mode2[m][n]=1; } else if(mode1[m][n]==4) { m1=m; n1=n; temp->next = NULL; } } } else if( z==2 && ( temp->prev==NULL || temp->prev->dir!=0) ) { m = temp->x;n = temp->y-1; if(m>=0 && m<=y && n>=0 && n<=x&& mode2[m][n]==0) { if(mode1[m][n]==0) { temp->dir = z; temp->next = (pSta)malloc(sizeof(Sta)); temp->next->prev = temp; temp = temp->next; temp->x = m; temp->y = n; temp->dir = 0; temp->serial = ++num; temp->next = (pSta)1; z = -1; mode2[m][n]=1; } else if(mode1[m][n]==4) { m1=m; n1=n; temp->next = NULL; } } } else if( z==3 && ( temp->prev==NULL || temp->prev->dir!=1) ) { m = temp->x+1;n = temp->y; if(m>=0 && m<=y && n>=0 && n<=x&& mode2[m][n]==0) { if(mode1[m][n]==0) { temp->dir = i; temp->next = (pSta)malloc(sizeof(Sta)); temp->next->prev = temp; temp = temp->next; temp->x = m; temp->y = n; temp->dir = 0; temp->serial = ++num; temp->next = (pSta)1; z = -1; mode2[m][n]=1; } else if(mode1[m][n]==4) { m1=m; n1=n; temp->next = NULL; } } } if(temp->next==NULL) break; if(z==3)//到最后路劲依然无解，则出栈 { if(temp->prev!=NULL) { temp = temp->prev; free(temp->next); z = temp->dir; } else { printf("此迷宫无解\n"); return 0; } } } temp=head->next; tail=tail->next; while(temp!=NULL) { printf("%d,%d\n",temp->y,temp->x); } printf("%d,%d\n",temp->y,temp->x); printf("%d,%d\n",n1,m1); return 0;}
总是报错。。。
[解决办法]
#include<queue>
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int x1,x2,y1,y2;
int ac[9][9];
int he[]={1,-1,0,0},zo[]={0,0,-1,1};
int ok[9][11]=
{
1 1 1 1 1 1 1 1
1 0 1 1 0 1 0 1
1 0 1 0 0 1 0 1
1 1 0 3 1 0 1 1
1 0 0 1 0 0 4 1
1 0 0 0 0 1 1 1
1 0 1 0 0 1 0 1
1 0 1 0 0 0 1 1
1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1
};
struct shu
{
int x,y,step;
};
int BFS()
{
queue<shu>q;//队列容器
int a,b,i;
shu bfs={x1,y1,0};
ac[x1][y1]=1;
q.push(bfs);//入队
while(!q.empty())//队列是否为空
{
bfs=q.front();//出对首
if(bfs.x==x2&&bfs.y==y2)
break;
q.pop();//出对
for(i=0;i<4;i++)
{ a=bfs.x+he[i];
b=bfs.y+zo[i];
if(a>0&&a<=8&&b>0&&b<=9&&ac[a][b]==0&&ok[a][b]==0)
{ shu bb={a,b,bfs.step+1};
q.push(bb);
ac[a][b]=1;
}
}
}
/*while(!q.empty())
q.pop();*/
return bfs.step;
}
int main()
{
int x,cc;
scanf("%d",&x);
while(x--)
{ memset(ac,0,sizeof(ac));
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
cc=BFS();
printf("%d\n",cc);
}
return 0;
}