迷宫问题,菜鸟求解...
标题: 迷宫问题
时 限: 100000 ms
内存限制: 100000 K
总时限: ms
描述: 迷宫问题
迷宫是一个二维矩阵,其中1为墙,0为路,3为入口,4为出口.要求从入口开始,从出口结束,按照 下,左,上,右 的顺序来搜索路径.
输入: 迷宫宽度w 迷宫高度h
迷宫第一行
迷宫第二行
...
迷宫第h 行
输出: 入口横坐标1 入口纵坐标1
横坐标2 纵坐标2
横坐标3 纵坐标3
横坐标4 纵坐标4
...
横坐标n-1 纵坐标n-1
出口横坐标n 出口纵坐标n
输入样例: 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
输出样例: 3 3
2 3
2 4
2 5
3 5
3 6
3 7
4 7
4 6
4 5
4 4
5 4
6 4
老师让用栈......可是不知道怎么试探四个方向...
[解决办法]
#include <stdio.h>#define MAX_WIDTH (128)#define MAX_HEIGHT (128)#define MAX_STACK_SIZE (MAX_WIDTH * MAX_HEIGHT)#define STACK_PUSH(stack, xx, yy) do {\ stack.array[stack.count].x = (xx);\ stack.array[stack.count++].y = (yy);\} while (0)#define STACK_POP(stack) stack.count--struct pos { int x; int y;};struct pos_stack { int count; struct pos array[MAX_STACK_SIZE];};struct direction { int dx; int dy;};int main(){ int width, height, i, j, top, x, y; int map[MAX_HEIGHT][MAX_WIDTH]; struct pos_stack my_stack; struct direction directions[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; my_stack.count = 0; scanf("%d %d", &width, &height); for (i = 0; i < height; i++) { for (j = 0; j < width; j++) { scanf("%d", &map[i][j]); if (map[i][j] == 3) { map[i][j] = 2; STACK_PUSH(my_stack, j, i); } } } while (my_stack.count > 0) { top = my_stack.count - 1; for (i = 0; i < 4; i++) { x = my_stack.array[top].x + directions[i].dx; y = my_stack.array[top].y + directions[i].dy; if (map[y][x] == 4) { map[y][x] = 2; STACK_PUSH(my_stack, x, y); goto print_result; } else if (map[y][x] == 0) { map[y][x] = 2; STACK_PUSH(my_stack, x, y); break; } } if (4 == i) STACK_POP(my_stack); }print_result: for (i = 0; i < my_stack.count; i++) printf("%d %d\n", my_stack.array[i].x, my_stack.array[i].y); if (my_stack.count == 0) printf("No result\n"); return 0;}