-
Notifications
You must be signed in to change notification settings - Fork 0
/
day15_1.cpp
48 lines (40 loc) · 1.15 KB
/
day15_1.cpp
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
#include <bits/stdc++.h>
using namespace std;
// dijkstra on grid?
int main() {
freopen("input.txt", "r", stdin);
string s;
vector<string> grid;
while (cin >> s)
grid.push_back(s);
int n = (int) grid.size(), m = (int) grid[0].size();
const int INF = 1e9;
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 2e9));
vector<vector<bool>> vis(n + 1, vector<bool>(m + 1));
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.emplace(0, 0);
dp[0][0] = 0;
while (!q.empty()) {
auto [_, pt] = q.top();
int x = pt / m, y = pt % m;
q.pop();
if (vis[x][y]) {
continue;
}
vis[x][y] = true;
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
auto in = [&](int x, int y) {
return (x >= 0 && x < n && y >= 0 && y < m);
};
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (in(nx, ny) && !vis[nx][ny]) {
dp[nx][ny] = min(dp[nx][ny], (grid[nx][ny] - '0') + dp[x][y]);
q.emplace(dp[nx][ny], nx * m + ny);
}
}
}
cout << dp[n - 1][m - 1] << '\n';
return 0;
}