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
| #include<bits/stdc++.h>
#define MAXN 105
using namespace std;
int dir[4][2] = {
{0, 1},
{1, 0},
{0, -1},
{-1, 0},
};
struct pos{
int x,y;
int cost;
bool operator<(const pos& a) const
{
return cost < a.cost;
}
};
int Map[MAXN][MAXN], cost[MAXN][MAXN], n, m;
int dist[MAXN][MAXN] = {0};
pos End;
vector<pos> MapNeighbor(pos t)
{
vector<pos> ret;
for (int i = 0; i < 4; i++)
{
pos a = pos{t.x + dir[i][0], t.y + dir[i][1]};
if (a.x > 0 && a.y > 0 && a.x <= n && a.y <= m && Map[a.x][a.y] != 1 && dist[a.x][a.y] == 0)
{
ret.push_back(a);
}
}
return ret;
}
inline int getcost(pos x) {return (abs(x.x - End.x) + abs(x.y - End.y));}
bool Astar(pos start)
{
priority_queue<pos> frontier;
frontier.push(start);
cost[start.x][start.y] = 0;
dist[start.x][start.y] = 0;
while (!frontier.empty())
{
pos t = frontier.top();
if (Map[t.x][t.y] == 2)
{
return true;
}
frontier.pop();
vector<pos> next = MapNeighbor(t);
for (auto i : next)
{
dist[i.x][i.y] = dist[t.x][t.y] + 1;
if (getcost(t) + t.cost < i.cost || i.cost == 0)
{
i.cost = getcost(t) + t.cost;
frontier.push(i);
}
}
}
return false;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> Map[i][j];
if (Map[i][j] == 2)
End.x = i, End.y = j;
}
Astar(pos{1, 1});
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
printf("%3d ", dist[i][j]);
cout << endl;
}
return 0;
}
|
