1.Find the path in a maze
2.others' thinking
First, we need a stack to put the node. initalized a two dimensions array to put the maze. And a stack is include the factorys, "i" to define the node's row "j" to define the node's colum and "di" is a label, if it's true, that means that there's a node could be put in the path that next to this node, else that means that the next node's next is blocked and the next node's label of the maze could be put -1 to avoid repreat.
At first, put the begin node into the stack and analysis if the node is the end, if it's, then cout all the nodes int the stack and that's a path that we find in this way. else, we define the
3.(1)solution with the stack method
#include<iostream>
#define Colum 10
#define Row 10
#define Maxsize 100
using namespace std;
int background[Row][Colum]={
1,1,1,1,1,1,1,1,1,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,1,0,0,0,1,0,1,
1,0,0,0,0,1,1,0,0,1,
1,0,1,1,1,0,0,0,0,1,
1,0,0,0,1,0,0,0,0,1,
1,0,1,0,0,0,1,0,0,1,
1,0,0,1,1,0,1,1,0,1,
1,0,0,0,0,0,0,0,0,1,
1,1,1,1,1,1,1,1,1,1};
struct node{
int di;//记录下一个可走的方向
int i;//记录行
int j;//记录列
}st[Maxsize];
int top=-1;//初始化栈
int findpath(int bi,int bj,int ei,int ej){
top++;
int i,j,di, find=0;
st[top].i=bi;
st[top].j=bj;
st[top].di=-1;
while(top>-1){
if((st[top].i==ei)&&(st[top].j=ej)){
while(top>-1){
cout<<"路径为："<<endl;
cout<<"("<<st[top].i<<","<<st[top].j<<") ";
top--;
if(top%5==0){cout<<endl;}
}
return 1;
}
find=0;
while(di<4&&find==0){
di++;
switch(di){
case 0:i=st[top].i-1;j=st[top].j;break;
case 1:i=st[top].i;j=st[top].j+1;break;
case 2:i=st[top].i+1;j=st[top].j;break;
case 3:i=st[top].i;j=st[top].j-1;break;
}
if(background[i][j]==0)find=1;
}
if(find==1){
st[top].di=di;
top++;
st[top].i=i;st[top].j=j;st[top].di=-1;
background[i][j]=-1;
}
else{background[st[top].i][background[st[top].j]]=0;top--;}
}
return 0;
}
int main(){
findpath(1,1,8,8);
return 0;
}
(2)solution with the queue method
To find the shortest path of the maze is meaningful to use a queue to put the nodes that could leads to the destination of the maze.
Define the maze with a two dimensons array. Define the queue structure with a abscissa and a ordinate and an integer variable namly "pri" to indicate the node's previous node's subscript(下标). Define two global variables to indacate the head of the queue and the tail of the queue separately namely "front" and "rear". Initializate the queue with the begin node's abscissa and ordinate and the -1 equals to the pri.
Then, while the queue is not empty, analysis the tail node if it's equals to the end of the maze, then the output function works. Else, make the value of the node in the maze -1 to avoid repetition. and then to check the arounds nodes' maze value, if it's vales 0, then put the node into the queue and at the same time value the variable "find" 1, and the node's pri values to the front node's subscript.
The output function is to find the head of the queue based the front's node's pri value, and then output the whole nodes that leads to the destination of the maze.
Summary:
Clearly know what you are doing and what do you want and know what will happen and how to get your solution. It's difficult for me. The beginning is always much hard, come on for myself.
