Contents
Problem
找起點到目的地的最短路。
Solution
這裡試了兩種方法，BFS 和 A*，
但 A* 並沒有比較快就是了，heuristic 選用常見的 Manhattan distance。
Code
有一行不知為何寫在上面，hexo 似乎會出錯…
(http://sessionch.com/hexo/hexo-common-markdown.html)
BFS1
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
using namespace std;
typedef pair<int, int> pos;
const int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int dis[N][N];
int R, C;
inline int input()
{
int n = 0;
char c;
while ((c = getchar()) != '\n' && c != ' ')
n = n * 10 + c - '0';
return n;
}
inline bool in_bound(int r, int c)
{
return r >= 0 && c >= 0 && r < R && c < C;
}
int BFS(pos &src, pos &des)
{
queue<pos> Q;
Q.push(src);
dis[src.first][src.second] = 1;
while (!Q.empty())
{
pos now = Q.front();
Q.pop();
for (int i = 0; i < 4; ++i)
{
int r = now.first + dir[i][0], c = now.second + dir[i][1];
if (in_bound(r, c) && dis[r][c] == 0)
{
dis[r][c] = dis[now.first][now.second] + 1;
pos next(r, c);
if (next == des)
return dis[des.first][des.second] - 1;
Q.push(next);
}
}
}
return -1;
}
int main()
{
//freopen("test.out", "w", stdout);
while (scanf("%d%d", &R, &C) && R)
{
int n, r, c, x;
scanf("%d", &n);
getchar();
for (int i = 0; i < n; ++i)
{
r = input();
x = input();
//scanf("%d%d", &r, &x);
for (int j = 0; j < x; ++j)
{
c = input();
//scanf("%d", &c);
dis[r][c] = -1;
}
}
pos src, des;
scanf("%d%d%d%d", &src.first, &src.second, &des.first, &des.second);
printf("%d\n", BFS(src, des));
//init
for (int i = 0; i < R; ++i)
memset(dis[i], 0, sizeof dis[i]);
}
return 0;
}
A*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
using namespace std;
typedef pair<int, int> pos;
typedef pair<pos, int> node;
const int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
bool bomb[N][N];
int dis[N][N];
int R, C;
inline bool in_bound(pos &p)
{
return p.first >= 0 && p.second >= 0 && p.first < R && p.second < C;
}
inline int heuristic(pos &a, pos &b)
{
//Manhattan distance
return abs(a.first - b.first) + abs(a.second - b.second);
}
int a_star(pos &src, pos &des)
{
priority_queue<node, vector<node>, bool (*)(const node &, const node &)> PQ([](const node &a, const node &b) -> bool {
return a.second > b.second;
});
PQ.emplace(src, 0);
bomb[src.first][src.second] = true;
for (int i = 0; i < R; ++i)
fill(dis[i], dis[i] + C, 1e9);
dis[src.first][src.second] = 0;
while (true)
{
pos now = PQ.top().first;
PQ.pop();
if (now == des)
return dis[des.first][des.second];
bomb[now.first][now.second] = true;
for (int i = 0; i < 4; ++i)
{
pos next(now.first + dir[i][0], now.second + dir[i][1]);
if (in_bound(next) && !bomb[next.first][next.second])
{
if (dis[next.first][next.second] > dis[now.first][now.second] + 1)
{
dis[next.first][next.second] = dis[now.first][now.second] + 1;
PQ.emplace(next, heuristic(next, des) + dis[next.first][next.second]);
}
}
}
}
return -1;
}
int main()
{
//freopen("test.out", "w", stdout);
while (scanf("%d%d", &R, &C) && R)
{
int n, r, c, x;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%d%d", &r, &x);
for (int j = 0; j < x; ++j)
{
scanf("%d", &c);
bomb[r][c] = true;
}
}
pos src, des;
scanf("%d%d%d%d", &src.first, &src.second, &des.first, &des.second);
printf("%d\n", a_star(src, des));
//init
for (int i = 0; i < R; ++i)
memset(bomb[i], false, sizeof bomb[i]);
}
return 0;
}