栈 算法1

发表于 | 分类于

迷宫问题

可扩展为：带路径，求最短，带权，等多种，基本思路如下

该实例要求：

用一个m×n的矩阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对给定的迷宫，求出找到的第一条从入口到出口的通路，或得到没有通路的结论。

我们指定:

(1) 迷宫的入口为矩阵的左上角（1,1），迷宫的出口为右下角（m,n）;

(2) 路径的探索顺序依次为”东南西北”（即：右下左上）。

输入

9 8
00100010
00100010
00001101
01110010
00010000
01000101
01111001
11000101
11000000

输出

(1,1,1)(1,2,2)(2,2,2)(3,2,3)(3,1,2)(4,1,2)(5,1,1)(5,2,1)(5,3,2)(6,3,1)(6,4,1)(6,5,4)(5,5,1)(5,6,1)(5,7,2)(6,7,2)(7,7,2)(8,7,2)(9,7,1)(9,8,0)

AC代码：

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
#include<stdio.h>
#pragma warning(disable:4996)；
int n,m,p,q,min=99999999;
int a[1000][1000], book[1000][1000] = {0};
int flag=0;
int p1[10000];
int p2[10000];
int p3[10000];
int top;
void dfs(int x,int y,int step)
{
	int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
	int tx,ty,k;
	if(flag==1)
	{
		return;
	}
	if(x==n&&y==m)
	{
		flag=1;
		top=step;
		return;
	}
	for(k=0;k<4;k++)
	{
		tx=x+next[k][0];
		ty=y+next[k][1];
		if(tx<1||tx>n||ty<1||ty>m)
		continue;
		
		if(a[tx][ty]==0&&book[tx][ty]==0)
		{
			book[tx][ty]=1;
			p1[step]=x;
			p2[step]=y;
			p3[step]=k+1;
			dfs(tx,ty,step+1);
			if (flag == 1)
			{
				return;
			}
			
			book[tx][ty]=0;
		}
			
	}
	return;
 }
  int main(void)
{
	int i,j;
	scanf("%d%d\n",&n,&m);
	char ls[1000];
	for(i=1;i<=n;i++)
	{
		gets(ls);
		for(j=1;j<=m;j++)
		{
			a[i][j]=ls[j-1]-'0';
		}
	}
	book[1][1]=1;
	p1[top]=1;
	p2[top]=1;
	p3[top]=1;
	
	
	
	
	dfs(1,1,1);
	
	if (flag == 1)
	{
		for (i = 1; i < top; i++)
		{
			printf("(%d,%d,%d)", p1[i], p2[i], p3[i]);
			
		}
		printf("(%d,%d,%d)", n, m, 0);
	}
	else
	{
	}
	return 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
#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable:4996)；
int cmp(char a, char b)
{
	if (a == '*' || a == '/')
	{
		if (b == '+' || b == '-')
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}
	else if(a== '+' || a == '-')
	{
		if (b == '+' || b == '-')
		{
			return 0;
		}
		else
		{
			return -1;
		}
	}
	else
	{
		return -1;
	}
}
int isnum(char a)
{
	if (a >= 'a'&&a <= 'z')
	{
		return 1;
	}
	else
		return 0;
}
int main(void)
{
	char q1[1000] = {0};
	char q2[1000] = {0};
	int t1=1, t2=0;
	char o[1000] = {0};
	int t3=0;
	scanf("%s", q2);
	char ch = q2[t2];
	t2++;
	while (ch != '\0')
	{
		if (isnum(ch))
		{
			o[t3] = ch;
			t3++;
			ch = q2[t2];
			t2++;
		}
		else
		{
			if (ch == ')')
			{
				
				while (q1[t1-1] != '(') {
					
					t1--;
					o[t3] = q1[t1];
					t3++;
				} 
				t1--;
				ch = q2[t2];
				t2++;
			}
			else if (ch == '(')
			{
				q1[t1] = ch;
				t1++;
				ch = q2[t2];
				t2++;
			}
			else
			{
				if (cmp(q1[t1 - 1], ch) < 0)
				{
					q1[t1] = ch;
					t1++;
					ch = q2[t2];
					t2++;
				}
				else if (cmp(q1[t1 - 1], ch) > 0)
				{
					t1--;
					o[t3] = q1[t1];
					t3++;
				}
				else
				{
					t1--;
					o[t3] = q1[t1];
					t3++;
				}
			}
			
		
		}
	}
	while (t1 != -1)
	{
		t1--;
		o[t3] = q1[t1];
		t3++;
	}
	o[t3] = 0;
	printf("%s", o);
}