本文共 4179 字，大约阅读时间需要 13 分钟。
#define __STACK_H__ #include #include #include #define ROW 10#define COL 10typedef int DataType;typedef struct Coordinate{ intx; inty;}Coo;typedef struct Stack{ Coo cde[40]; intsz;}Stack;typedef struct MAP{ Coo cde; intmap[ROW][COL];}MAP;void Initstack(Stack * stack){ assert(stack != NULL); memset(stack, sizeof(stack->cde), 80); stack->sz = 0;}void Pushstack(Stack * stack, Coo d){ assert(stack != NULL); stack->cde[stack->sz] = d; stack->sz++;}void Popstack(Stack * stack){ Coo z; assert(stack != NULL); z.x = 0; z.y = 0; stack->cde[stack->sz - 1] =z; stack->sz--;}Coo Topstack(Stack stack){ returnstack.cde[stack.sz - 1];}int Lengthstack(Stack* stcak){ returnstcak->sz;}void InitMap(MAP* m, Coo enter){ assert(m != NULL); intMap[ROW][COL] = { { 0,0,0,0,0,0,0,0,0,0 }, { 0,1,1,1,1,1,1,1,1,0 }, { 0,1,0,0,0,0,0,0,1,0 }, { 0,1,0,1,1,1,1,1,1,0 }, { 0,1,0,0,0,0,0,0,0,0 }, { 0,1,0,1,1,1,1,1,1,0 }, { 0,1,0,1,0,0,1,0,1,0 }, { 0,1,0,1,0,1,1,0,0,0 }, { 0,1,1,1,0,1,1,1,1,1 }, { 0,0,0,0,0,0,0,0,0,0 } }; int i, j = 0; for(i = 0; i < ROW; i++) { for(j = 0; j < COL; j++) { m->map[i][j] = Map[i][j]; } }}void PrintMap(MAP* m){ assert(m != NULL); inti, j = 0; for(i = 0; i < ROW; i++) { for(j = 0; j < COL; j++) { printf("%3d ", m->map[i][j]); } printf("\n"); }}int IsValid(MAP* m, Coo enter)//入口再边界，并且结点的数为{ assert(m); if(enter.x == 0 || enter.y == ROW - 1 || enter.y == 0 || enter.x == COL - 1) {if(m->map[enter.x][enter.y] == 1) return1; } return0;}int IsPass(MAP* m,Coo c, Coo d)//d必须在地图中，{ assert(m != NULL); if(d.x >= 0 && d.x < ROW&&d.y >= 0 && d.y map[d.x][d.y] == 1 || (m->map[d.x][d.y]>m->map[c.x][c.y]))//结点为或者下个结点大于当前结点 return1; } return0;}int IsExit(MAP* m, Coo d, Coo enter)//出口在边界并且不是入口{ assert(m != NULL); if((d.x == 0 || d.y == ROW - 1 || d.y == 0 || d.x == COL - 1)) { if(d.x != enter.x||d.y != enter.y) { return1; } } return0;}void EvaluateStack(Stack * stack, Stack * shortstack){ assert(stack); inti, j = Lengthstack(stack); for(i = 0; i < j; i++) { Pushstack (shortstack,stack->cde[i]); } }void PassMaze(MAP* m, Coo enter, Stack * stack, Stack *shortstack){ assert(m != NULL); Coo cur, next; Coo enter1; enter1.x = 9; enter1.y = 1; if(IsValid(m, enter) == 1) { m->map[enter.x][enter.y] = 2; } Pushstack(stack, enter); cur = Topstack(*stack); //递归的出口 if(IsExit(m, enter, enter1) == 1) { if(Lengthstack(stack) > Lengthstack(shortstack)&&shortstack->sz==0)//最短路径的栈为空，说明是第一次走到出口， { //找到的第一条路径 EvaluateStack(stack,shortstack); } if(Lengthstack(stack) < Lengthstack(shortstack))//当前的栈小于已经保存了最短路径的栈，需要更新最短路径的栈 { shortstack->sz = 0; EvaluateStack(stack,shortstack); } Popstack(stack); return; } //往上走 next = cur; next.x = cur.x - 1; if(IsPass(m, cur, next) == 1) { m->map[next.x][next.y]= m->map[cur.x][cur.y] + 1; PassMaze(m, next, stack,shortstack); } //往左走 next = cur; next.y = cur.y - 1; if(IsPass(m, cur, next) == 1) { m->map[next.x][next.y] =m->map[cur.x][cur.y] + 1; PassMaze(m, next, stack,shortstack); } //往右走 next = cur; next.y = cur.y + 1; if(IsPass(m, cur, next) == 1) { m->map[next.x][next.y] =m->map[cur.x][cur.y] + 1; PassMaze(m, next, stack,shortstack); } //往下走 next = cur; next.x = cur.x + 1; if(IsPass(m, cur, next) == 1) { m->map[next.x][next.y] =m->map[cur.x][cur.y] + 1; PassMaze(m, next, stack, shortstack); } //走不通 Popstack(stack);} int main(){ MAP m; Coo enter; Stack stack, shortstack; Initstack(&stack); Initstack(&shortstack); enter.x = 9; enter.y = 1; InitMap(&m, enter); PrintMap(&m); PassMaze(&m,enter,&stack,&shortstack); printf("\n"); PrintMap(&m); printf("最短路径为:\n"); inti,a = shortstack.sz; for(i = 0; i < a; i++) { printf("(%d,%d)", shortstack.cde[i].x, shortstack.cde[i].y); } system("pause"); return0;}
转载地址：http://jkrgn.baihongyu.com/