HDU/HDOJ 1026 Ignatius and the Princess I(BFS广搜)

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1026

此题非常非常经典。

搜索用BFS,队列实现,然后输出路径用栈实现。

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
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
 
typedef struct Node{
	int x, y, cost;
	int prex, prey;
}Node;
 
int N, M;
char maze[105][105];   // 记录初始输入
Node path[105][105];   // 记录路径
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
// 判断(x, y)是否可行
bool isOK(int x, int y)
{
	if(x>=0 && x<N && y>=0 && y<M && maze[x][y]!='X')
		return 1;
	else
		return 0;
}
 
void Init()
{
    int i, j;
    for(i = 0; i < N; ++i)
        for(j = 0; j < M; ++j)
            path[i][j].cost = -1;
}
 
void backPath(int x, int y)
{
    stack<Node> S;
	Node a, b;
    int cc = 1, tmp;
 
    cout << "It takes " << path[N - 1][M - 1].cost 
		<< " seconds to reach the target position, let me show you the way." << endl;
    a = path[N - 1][M - 1];
    while(1)
    {
        if(a.x == 0 && a.y == 0)
            break;
        S.push(a);
        a = path[a.prex][a.prey];
    }
 
    a = path[0][0];
 
    while(!S.empty())
    {
        b = S.top();
        S.pop();
        if(maze[b.x][b.y] == '.')
            cout << cc++ << "s:(" << a.x << "," << a.y << ")->(" << b.x << "," << b.y << ")" << endl;
        else
        {
            cout << cc++ << "s:(" << a.x << "," << a.y << ")->(" << b.x << "," << b.y << ")" << endl;
            tmp = maze[b.x][b.y] - '0';
            while(tmp--)
                cout << cc++ << "s:FIGHT AT (" << b.x << "," << b.y << ")" <<endl;
        }
        a = b;
    }
    cout<<"FINISH"<<endl;
}
 
 
int BFS(int x, int y)
{
	queue<Node> Q;
	Node a, b;
	a.x = a.y = a.cost = a.prex = a.prey = 0;
	if(maze[0][0] != '.')
		a.cost = maze[0][0] - '0';
	path[0][0] = a;
	Q.push(a);
 
	while(!Q.empty())
	{
		a = Q.front();
		Q.pop();
		for(int i=0; i<4; ++i)
		{
			b.x = a.x + dir[i][0];
			b.y = a.y + dir[i][1];
			if(!isOK(b.x, b.y))
				continue;
			if(maze[b.x][b.y] == '.')
				b.cost = a.cost + 1;
			else
				b.cost = a.cost + maze[b.x][b.y]-'0' + 1;
			if(b.cost < path[b.x][b.y].cost || path[b.x][b.y].cost == -1)
            {
                b.prex = a.x; 
				b.prey = a.y;
                path[b.x][b.y] = b;
                Q.push(b);
            }
		}
	}
    if(path[N - 1][M - 1].cost == -1)
    {
        cout << "God please help our poor hero." << endl;
        cout << "FINISH" << endl;
        return 0;
    }
	backPath(N-1, M-1);
}
 
 
int main()
{
	//freopen("input.txt", "r", stdin);
	while(cin >> N >> M)
	{
		memset(maze, 0, sizeof(maze));
		for(int i=0; i<N; ++i)
			for(int j=0; j<M; ++j)
				cin >> maze[i][j];
		Init();
		BFS(0, 0);
	}
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注