问题描述
算法
变量解释:
- di : 方向 (0表示右边,1表示下边,2表示左边,3表示上边)【偏移量技巧】
- X位置的元素: 地图数组的元素
算法步骤:
1. 将起始位置(入口)压入栈中,栈存放路径、栈顶就是当前所处位置A
2. 判断当前位置是否为出口位置,如果是遍历栈;若不是,继续下一步
3. 从右边开始顺时针穷举每一个方向,若有一个方向的位置B是可以通过的,则压入B位置,并且将A位置的di更改为现在的di
、B位置的元素更改为-1(说明走过了);若穷举完了也没有找到一个可以通过的方向的话,那么就弹出位置A(说明进入死胡同了)并且将这个位置的元素更改为0
4. 若栈为空了,那么就说明没有解
代码
#include<iostream>
#include<stack>
using namespace std;
#define STACK_INIT_SIZE 100
#define MAXSIZE 10000
#define STACKINREMENT 10
typedef struct{
int di; // 上下左右的序号
int x; // 坐标
int y;
}Box;
typedef Box EleType;
int maze[10][10] ={
{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,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
typedef struct{
EleType data[MAXSIZE];
int top;
}SqStack;
void initStack(SqStack& stack)
{
stack.top = -1;
}
bool push(SqStack& stack,EleType x)
{
if(stack.top >= MAXSIZE - 1) return false;
stack.data[++ (stack.top)] = x;
return true;
}
bool pop(SqStack& stack)
{
if(stack.top == -1) return false;
stack.top--;
return true;
}
bool isEmpty(SqStack& stack)
{
return stack.top == -1;
}
EleType getTop(SqStack& stack)
{
return stack.data[stack.top];
}
//----------------------------------------------
bool maze_solve(int xs,int ys,int xe,int ye)
{
SqStack stack;
initStack(stack);
Box e;
bool find; // 是否找到了下一个可以通过的地方
e.x = xs,e.y = ys;
e.di = -1; //初始化栈顶元素
push(stack,e);
int x,y,di,x1,y1;
while(isEmpty(stack) == false)
{
EleType e = getTop(stack);
x = e.x,y = e.y,di = e.di;
if(x == xe && y == ye)
{
cout << "找到了一条路径:" << endl;
while(isEmpty(stack) == false)
{
cout << "(" << getTop(stack).x << "," << getTop(stack).y << ")" <<" ";
pop(stack);
}
return true;
}
find = false;
while(di < 4 && !find)
{
di ++;
switch(di)
{
case 0:x1=x-1; y1=y; break;
case 1:x1=x; y1=y+1; break;
case 2:x1=x+1; y1=y; break;
case 3:x1=x; y1=y-1; break;
}
if (maze[x1][y1]==0) find=true;
}
if(find)
{
stack.data[stack.top].di = di;
e.x = x1,e.y = y1,e.di = -1;
push(stack,e);
maze[x1][y1] = -1;
}
else
{
EleType e = getTop(stack);
pop(stack);
maze[e.x][e.y] = 0;
}
}
return false;
}
int main()
{
maze_solve(1,1,8,8);
}