老鼠走迷宫问题

问题描述

n行m列的经典01迷宫问题，起点是(1,1)，终点是(n,m)，以往都是递归写法非常easy，这次数据结构的课设作业要求用栈链写，打开新世界的大门…

##思考

  1. 沿用老套路，用2个常量数组来表示行走的方向。
  2. 用栈来保存行走的路径。
  3. 当无路可走时，当前坐标出栈，回溯到上一步，继续尝试。所以当所有的路径都尝试过了还是没有找到出路时，代表着此迷宫无解，此时栈为空。
  4. 用结构体成员from表示这一步走来的方向，用check数组表示是否访问过，以免回路。
  5. 初始化map全是1，相当于在迷宫外围加了一圈墙壁，防止越界。

大概只想到这么多。

样例输入：
3 3
0 1 0
0 1 0
0 0 0

3 3
0 1 1
0 1 1
0 1 0

5 5
0 1 0 0 0
0 0 0 1 0
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#pragma warning(disable:4996)
#include "stdafx.h"
#include <stdio.h>
#include <malloc.h>
const int move_x[] = { 0,0,0,1,-1 };
const int move_y[] = { 0,1,-1,0,0 };
int map[100][100],check[100][100];
struct node 
{
	int x, y, from;
	struct node *next;
};
struct node *top;
void show();
void Go(int n, int m);
void Pop();
struct node* Top();
void Push(struct node* p);
int Empty();
void show()
{
	int i;
	struct node *p;
	int x[1000], y[1000];
	int len;
	len = 0;
	while (Empty() == 0)
	{
		len++;
		p = Top();
		x[len] = p->x;
		y[len] = p->y;
		Pop();
	}
	printf("steps=%d\n", len);
	for (i = len; i > 0; i--)
		printf("(%d, %d)\n", x[i],y[i]);
}
int Empty()
{
	if (top==NULL) return 1;
	return 0;
}
void Pop()
{
	struct node *p;
	p = top;
	top = p->next;
	free(p);
}
struct node* Top()
{
	return top;
}
void Push(struct node *p)
{
	p->next = top;
	top = p;
}
void Go(int n, int m)
{
	struct node *p;
	int i;
	int nx, ny, come, find;
	
	p = (struct node *)malloc(sizeof(struct node));
	p->from = 0;
	p->x = 1;
	p->y = 1;
	Push(p);
	check[1][1] = 1;
	top->next = NULL;
	come = 0;
	while (1)
	{
		find = 0;
		for (i = come + 1; i <= 4; i++)
		{
			nx = top->x + move_x[i];
			ny = top->y + move_y[i];
			if (check[nx][ny] == 0 && map[nx][ny] == 0)
			{
				p = (struct node *)malloc(sizeof(struct node));
				p->x = nx;
				p->y = ny;
				p->from = i;
				Push(p);
				come = 0;
				find = 1;
				check[nx][ny] = 1;
				if (nx == n && ny == m)
				{
					show();
					return;
				}
				break;
			}
		}
		if (find == 0)
		{
			p = Top();
			nx = p->x;
			ny = p->y;
			come = p->from;
			Pop();
		}
		find = 0;
		if (top == NULL)
		{
			printf("There's no way out!\n");
			return;
		}
	}
}
int main()
{
	int n, m;
	int i, j;
	char ch;
	while (scanf("%d%d", &n, &m) && n && m)
	{
		memset(check, 0, sizeof(check));
		for (i = 0; i < 100; i++)
			for (j = 0; j < 100; j++) map[i][j] = 1;
		for (i = 1; i <= n; i++)
			for (j = 1; j <= m; j++)
				scanf("%d", &map[i][j]);
		if (map[1][1] == 1 || map[n][m] == 1)
		{
			printf("There is no way out!\n");
			continue;
		}
		Go(n, m);
	}
    return 0;
}
文章目录
  1. 1. 问题描述
|