利用栈实现迷宫求解通路。
关键点:1.明确四个方向的顺序(顺时针或逆时针)
2.做标记避免重复走到已走的方块
3.找到可走的方块要进栈保存信息
4.若当前方块没路走了,要出栈并且此位置归0(还原为可走方块)
#include <stdio.h> int map[10][10] = { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,0,0,1,1,1}, {1,0,0,1,0,0,0,1}, {1,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1} }; int killmaze(int si,int sj,int ei,int ej) { struct { int i; //当前方块行号 int j; //当前方块列号 int di; //下一个相邻可走方位号 } st[100]; int top = -1; //初始化栈顶指针 int i,j,k,di,f; top++; //初始方块进栈 st[top].i = si; st[top].j = sj; st[top].di = -1; map[si][sj] = -1; while (top>-1) //栈不空则循环 { i = st[top].i; j = st[top].j; di = st[top].di; //取栈顶方块 if (i==ei&&j==ej) //找到出口! { printf("maze road is:\n"); for (k=0; k<=top; k++) { printf("\t(%d,%d) ",st[k].i,st[k].j); } printf("\n"); return 1; } else //没找到出口 { f = 0; while (di<4&&f==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 (map[i][j]==0) f = 1; //找到可走的(map是0) } if (f==1) //修改原栈顶元素di { st[top].di = di; top++; //下一个可走方块进栈(刚刚找到的可走的) st[top].i = i; st[top].j = j; st[top].di = -1; map[i][j] = -1; //避免重复走此方块 } else //没找到可走的方块 { map[st[top].i][st[top].j] = 0; //该方块变为其他路径可走(虽然这个方块往前走不了,但是这个方块可以走啊) top--; //该方块退栈(走到你这都没路了肯定退你啦) } } } return 0; } int main() { killmaze(1,1,4,6); return 0; }