#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation
#pragma GCC target("movbe") // byte swap
#pragma GCC target("aes,pclmul,rdrnd") // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")
typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define rrep(i, a, b) for (int i = (a) - 1; i >= int(b); i--)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
ll INF = 1000000000;
ll mod = 1e9 + 7;
#define int ll
#define float double
//
int R, C;
vector<string> grid;
pii S;
pii Ca;
vector<vector<int>> lr, rl, ud, du, visited;
//
vector<vector<vector<vector<pair<pii, int>>>>> dp;
void sol(int r, int c, int b, pii o, int steps)
{
if (grid[r][c] == '#') return; // ?
bool f = false;
rep(i, 0, dp[r][c][b].size()) {
if (dp[r][c][b][i].first.first == o.first && dp[r][c][b][i].first.second == o.second) {
// return; // dp[r][c][b][i].second; //
if (dp[r][c][b][i].second <= steps) return;
else dp[r][c][b][i].second = steps;
f = true;
}
}
if (!f) dp[r][c][b].push_back({o, steps});
int nsteps = steps + 1;
// walk
vector<pii> ps = {{du[r][c], c}, {ud[r][c], c}, {r, rl[r][c]}, {r, lr[r][c]}};
rep(i,0,4) {
if (r - 1 >= 0) {
sol(r - 1, c, 0, ps[i], nsteps);
}
if (r + 1 < R) {
sol(r + 1, c, 0, ps[i], nsteps);
}
if (c - 1 >= 0) {
sol(r, c - 1, 0, ps[i], nsteps);
}
if (c + 1 < C) {
sol(r, c + 1, 0, ps[i], nsteps);
}
}
if (b == 2) {
if (r - 1 >= 0) {
sol(r - 1, c, 2, {-1, -1}, nsteps);
}
if (r + 1 < R) {
sol(r + 1, c, 2, {-1, -1}, nsteps);
}
if (c - 1 >= 0) {
sol(r, c - 1, 2, {-1, -1}, nsteps);
}
if (c + 1 < C) {
sol(r, c + 1, 2, {-1, -1}, nsteps);
}
}
// portal
bool u = false;
if (r == 0) u = true;
else if (grid[r - 1][c] == '#') u = true;
bool d = false;
if (r == R - 1) d = true;
else if (grid[r + 1][c] == '#') d = true;
bool l = false;
if (c == 0) l = true;
else if (grid[r][c - 1] == '#') l = true;
bool ri = false;
if (c == C - 1) ri = true;
else if (grid[r][c + 1] == '#') ri = true;
bool p = u || d || l || ri;
if ((b == 1) || (b == 2 && p)) {
rep(i,0,4) {
sol(ps[i].first, ps[i].second, 1, {-1, -1}, nsteps);
}
}
else if (o.first != -1 && o.second != -1 && p) { //
sol(o.first, o.second, 1, {-1, -1}, nsteps);
}
}
int32_t main()
{
fast();
cin >> R >> C;
grid.assign(R, "");
rep(i,0,R) {
cin >> grid[i];
rep(j,0,C) {
if (grid[i][j] == 'S') S = {i, j};
if (grid[i][j] == 'C') Ca = {i, j};
}
}
lr.assign(R, vector<int>(C, -1));
rl.assign(R, vector<int>(C, -1));
ud.assign(R, vector<int>(C, -1));
du.assign(R, vector<int>(C, -1));
//
dp.assign(R, vector<vector<vector<pair<pii, int>>>>(C, vector<vector<pair<pii, int>>>(3, vector<pair<pii, int>>())));
//
rep(i,0,R) { // lr
lr[i][0] = 0;
rep(j,1,C) {
if (grid[i][j - 1] == '#') lr[i][j] = j;
else lr[i][j] = lr[i][j - 1];
}
}
rep(i,0,R) { // rl
rl[i][C-1] = C-1;
rrep(j,C-1,0) {
if (grid[i][j + 1] == '#') rl[i][j] = j;
else rl[i][j] = rl[i][j + 1];
}
}
rep(j,0,C) { // ud
ud[0][j] = 0;
rep(i,1,R) {
if (grid[i - 1][j] == '#') ud[i][j] = i;
else ud[i][j] = ud[i - 1][j];
}
}
rep(j,0,C) { // du
du[R - 1][j] = R - 1;
rrep(i,R - 1, 0) {
if (grid[i + 1][j] == '#') du[i][j] = i;
else du[i][j] = du[i + 1][j];
}
}
//
sol(S.first, S.second, 2, {-1, -1}, 0);
//
ll aa = INF;
rep(i,0,3) {
rep(j,0,dp[Ca.first][Ca.second][i].size()) {
aa = min(aa, dp[Ca.first][Ca.second][i][j].second);
}
}
cout << aa << "\n";
// cerr << endl;
// rep(i,0,R) {
// rep(j, 0, C) {
// cerr << visited[i][j] << " ";
// }
// cerr << endl;
// }
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
600 KB |
Output is correct |
| 3 |
Correct |
4 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
536 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
4 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
4 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
4 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
768 KB |
Output is correct |
| 3 |
Correct |
4 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
