#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <functional>
#include <queue>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define sz(a) a.size()
#define pb(a) push_back(a)
const ll INF = 1000000000;
vvll wall;
vvll dp;
vvll portal[4]; // for each of the 4 directions, get the distance to the wall...
pll start;
pll cake;
ll R, C;
vvb board;
ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};
void calc_wall();
void calc_goal();
void calc_portal();
bool dp_compare(pll a, pll b) {
if (dp[a.first][a.second] == dp[b.first][b.second]) {
return a < b;
}
return dp[a.first][a.second] < dp[b.first][b.second];
}
set<pll, decltype(dp_compare)*> BFS(dp_compare);
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> R >> C;
board.resize(R + 2);
char tmp;
board[0].resize(C + 2);
board[R + 1].resize(C + 2);
rep(j, 0, C + 2) {board[0][j] = false; board[R + 1][j] = false;}
rep(i, 1, R + 1) {
board[i].resize(C + 2);
board[i][0] = false;
board[i][C + 1] = false;
rep(j, 1, C + 1) {
cin >> tmp;
board[i][j] = (tmp != '#');
if (tmp == 'S') {
start = mp(i, j);
}
if (tmp == 'C') {
cake = mp(i, j);
}
}
}
R += 2;
C += 2;
wall.resize(R);
dp.resize(R);
rep(i, 0, 4) portal[i].resize(R);
rep(i, 0, R) {
wall[i].resize(C);
dp[i].resize(C);
rep(j, 0, 4) portal[j][i].resize(C);
rep(j, 0, C) dp[i][j] = INF;
}
// calculate supporting values
calc_wall();
calc_portal();
// do BFS in dp graph...
dp[start.first][start.second] = 0;
rep(i, 0, R) {
rep(j, 0, C) {
if (board[i][j]) BFS.insert(mp(i, j));
}
}
while (!BFS.empty()) {
pll pos = *BFS.begin();
BFS.erase(BFS.begin());
rep(k, 0, 4) {
// try walking
pll next = mp(pos.first + dx[k], pos.second + dy[k]);
if ((board[next.first][next.second]) && (dp[next.first][next.second] > dp[pos.first][pos.second] + 1)) {
BFS.erase(next);
dp[next.first][next.second] = dp[pos.first][pos.second] + 1;
BFS.insert(next);
}
// try shooting
next = mp(pos.first + (dx[k] * portal[k][pos.first][pos.second]), pos.second + (dy[k] * portal[k][pos.first][pos.second]));
if ((portal[k][pos.first][pos.second] >= 1) && (dp[next.first][next.second] > dp[pos.first][pos.second] + wall[pos.first][pos.second])) {
BFS.erase(next);
dp[next.first][next.second] = dp[pos.first][pos.second] + wall[pos.first][pos.second];
BFS.insert(next);
}
}
}
cout << dp[cake.first][cake.second] << endl;
return 0;
}
void calc_wall() {
vvb vis(R, vb(C, false));
vpll p, q;
rep(i, 0, R) {
rep(j, 0, C) {
if (!board[i][j]) {
q.pb(mp(i, j));
wall[i][j] = 0;
vis[i][j] = true;
}
}
}
while (!q.empty()) {
for (vpll::iterator itr = q.begin(); itr != q.end(); itr++) {
rep(d, 0, 4) {
pll next = mp(itr->first + dx[d], itr->second + dy[d]);
if ((next.first == -1) || (next.second == -1) || (next.first == R) || (next.second == C)) continue;
if (!vis[next.first][next.second]) {
vis[next.first][next.second] = true;
wall[next.first][next.second] = wall[itr->first][itr->second] + 1;
p.pb(next);
}
}
}
swap(p, q);
p.clear();
}
}
ll portal_dp(ll i, ll j, ll k) {
if (portal[k][i][j] == -2) portal[k][i][j] = portal_dp(i + dx[k], j + dy[k], k) + 1;
return portal[k][i][j];
}
void calc_portal() {
// setup before call dp
rep(i, 0, R) {
rep(j, 0, C) {
rep(k, 0, 4) {
portal[k][i][j] = -1 -(board[i][j]);
}
}
}
rep(i, 0, R) {
rep(j, 0, C) {
rep(k, 0, 4) {
portal_dp(i, j, k);
}
}
}
}
// There is a (RC)^3 dp
// There is also a (RC)^2 dp: if there are 2 portals then one should b-line to one of them
// For each cell we define the following distances:
// Distance to cell before nearest wall
// Distance to goal
// Then from each cell we can do one of 3 operations:
// Move a step up/down/left/right
// Shoot a portal to a wall up/down/left/right and go to nearest wall to appear at where we shot
// Move to goal
// This gives us a 9*RC dp with RC statest and 9 edges per state...
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
3 ms |
564 KB |
Output is correct |
13 |
Correct |
3 ms |
468 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
27 ms |
3772 KB |
Output is correct |
6 |
Correct |
28 ms |
3708 KB |
Output is correct |
7 |
Correct |
29 ms |
3872 KB |
Output is correct |
8 |
Correct |
27 ms |
3972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
2 ms |
596 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
3 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
27 ms |
3664 KB |
Output is correct |
15 |
Correct |
31 ms |
3816 KB |
Output is correct |
16 |
Correct |
31 ms |
3916 KB |
Output is correct |
17 |
Correct |
27 ms |
3872 KB |
Output is correct |
18 |
Correct |
33 ms |
4232 KB |
Output is correct |
19 |
Correct |
44 ms |
4876 KB |
Output is correct |
20 |
Correct |
42 ms |
4704 KB |
Output is correct |
21 |
Correct |
25 ms |
3776 KB |
Output is correct |
22 |
Correct |
27 ms |
3744 KB |
Output is correct |
23 |
Correct |
28 ms |
3800 KB |
Output is correct |
24 |
Correct |
39 ms |
4784 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
2 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
26 ms |
3884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
2 ms |
468 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
28 ms |
3748 KB |
Output is correct |
15 |
Correct |
28 ms |
3724 KB |
Output is correct |
16 |
Correct |
30 ms |
3916 KB |
Output is correct |
17 |
Correct |
27 ms |
3836 KB |
Output is correct |
18 |
Correct |
35 ms |
4232 KB |
Output is correct |
19 |
Correct |
47 ms |
4788 KB |
Output is correct |
20 |
Correct |
50 ms |
4696 KB |
Output is correct |
21 |
Correct |
27 ms |
3764 KB |
Output is correct |
22 |
Correct |
27 ms |
3796 KB |
Output is correct |
23 |
Correct |
29 ms |
3872 KB |
Output is correct |
24 |
Execution timed out |
1082 ms |
90736 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |