#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
typedef long long ll;
ll linf = 1e15+1;
inline void scoobydoobydoo(){
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
}
const int MAXN = 1e3+5;
bool arr[MAXN][MAXN];
int closestWall[MAXN][MAXN];
bool isVisited[MAXN][MAXN], firstVisited[MAXN][MAXN];
pair<int, int> portals[MAXN][MAXN][4];
vector<pair<int, int> > walls;
map<int, queue<pair<int, int> >> portsZ;
int main(){
scoobydoobydoo();
//cout << 2 << endl;
queue<vector<int>> q;
//cout << "g" << endl;
pair<int, int> start, ending;
int r, c; cin >> r >> c;
for (int i = 0; i <= c+1; i++){
arr[0][i] = false;
walls.push_back({0, i});
q.push({0, i, 0});
}
for (int i = 1; i <= r; i++){
arr[i][0] = false;
walls.push_back({i, 0});
q.push({i, 0, 0});
isVisited[i][0] = true;
firstVisited[i][0] = true;
for (int j = 1; j <= c; j++){
char l; cin >> l;
arr[i][j] = (l != '#');
if (l == '#'){
q.push({i, j, 0});
walls.push_back({i, j});
isVisited[i][j] = true;
firstVisited[i][j] = true;
}
if (l == 'S'){
start = {i, j};
}
if (l == 'C'){
ending = {i, j};
}
}
arr[i][c+1] = false;
walls.push_back({i, c+1});
q.push({i, c+1, 0});
isVisited[i][c+1] = true;
firstVisited[i][c+1] = true;
}
queue<vector<int>> ql;
ql.push({start.first, start.second, 0});
int highest = 0;
while (!ql.empty()){
int x = ql.front()[0];
int y = ql.front()[1];
int w = ql.front()[2];
ql.pop();
if (x == ending.first && y == ending.second){
highest = w;
break;
}
if (arr[x-1][y] && !firstVisited[x-1][y]){
firstVisited[x-1][y] = true;
ql.push({x-1, y, w+1});
}
if (arr[x+1][y] && !firstVisited[x+1][y]){
firstVisited[x+1][y] = true;
ql.push({x+1, y, w+1});
}
if (arr[x][y-1] && !firstVisited[x][y-1]){
firstVisited[x][y-1] = true;
ql.push({x, y-1, w+1});
}
if (arr[x][y+1] && !firstVisited[x][y+1]){
firstVisited[x][y+1] = true;
ql.push({x, y+1, w+1});
}
}
for (int i = 0; i <= c+1; i++){
arr[r+1][i] = false;
walls.push_back({r+1, i});
q.push({r+1, i, 0});
}
while (!q.empty()){
int i = q.front()[0];
int j = q.front()[1];
int w = q.front()[2];
closestWall[i][j] = w;
q.pop();
if (i+1 < r && arr[i+1][j] && !isVisited[i+1][j]){
q.push({i+1, j, w+1});
isVisited[i+1][j] = true;
}
if (i-1 >= 0 && arr[i-1][j] && !isVisited[i-1][j]){
q.push({i-1, j, w+1});
isVisited[i-1][j] = true;
}
if (j+1 < c && arr[i][j+1] && !isVisited[i][j+1]){
q.push({i, j+1, w+1});
isVisited[i][j+1] = true;
}
if (j-1 >= 0 && arr[i][j-1] && !isVisited[i][j-1]){
q.push({i, j-1, w+1});
isVisited[i][j-1] = true;
}
}
for (int i = 0; i <= r+1; i++){
for (int j = 0; j <= c+1; j++){
isVisited[i][j] = false;
}
}
for (auto& e : walls){
int i = e.first-1;
int j = e.second;
while (i >= 0 && arr[i][j]){
portals[i][j][0] = {e.first-1, e.second};
i--;
}
i = e.first+1;
while (i <= r+1 && arr[i][j]){
portals[i][j][1] = {e.first+1, e.second};
i++;
}
i = e.first;
j = e.second-1;
while (j >= 0 && arr[i][j]){
portals[i][j][2] = {e.first, e.second-1};
j--;
}
j = e.second+1;
while (j <= c+1 && arr[i][j]){
portals[i][j][3] = {e.first, e.second+1};
j++;
}
}
queue<vector<int> > pq;
pq.push({0, start.first, start.second});
//int last = 0;
while (!pq.empty()){
int x = pq.front()[1];
int y = pq.front()[2];
int w = -pq.front()[0];
//cout << x << " " << y << " " << w << endl;
pq.pop();
//if (vis[x][y])continue;
if (x == ending.first && y == ending.second){
cout << w << endl;
return 0;
}
int closest = closestWall[x][y];
//4 Dirs
if (arr[x+1][y] && !isVisited[x+1][y]){
pq.push({-(w+1), x+1, y});
isVisited[x+1][y] = true;
}
if (arr[x-1][y] && !isVisited[x-1][y]){
pq.push({-(w+1), x-1, y});
isVisited[x-1][y] = true;
}
if (arr[x][y+1] && !isVisited[x][y+1]){
pq.push({-(w+1), x, y+1});
isVisited[x][y+1] = true;
}
if (arr[x][y-1] && !isVisited[x][y-1]){
pq.push({-(w+1), x, y-1});
isVisited[x][y-1] = true;
}
//4 Portals
for (int i = 0; i < 4; i++){
pair<int, int> e = portals[x][y][i];
if (!isVisited[e.first][e.second] && w + closest <= highest){
portsZ[w+closest].push({e.first, e.second});
}
}
while (!portsZ[w+1].empty()){
int x1 = portsZ[w+1].front().first;
int y1 = portsZ[w+1].front().second;
portsZ[w+1].pop();
if (!arr[x1][y1])continue;
if (!isVisited[x1][y1]){
isVisited[x1][y1] = true;
pq.push({-(w+1), x1, y1});
}
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6488 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
4440 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6748 KB |
Output is correct |
10 |
Correct |
1 ms |
6744 KB |
Output is correct |
11 |
Correct |
2 ms |
7004 KB |
Output is correct |
12 |
Correct |
2 ms |
6748 KB |
Output is correct |
13 |
Correct |
1 ms |
6748 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
6748 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
10 ms |
13840 KB |
Output is correct |
6 |
Correct |
9 ms |
12504 KB |
Output is correct |
7 |
Correct |
7 ms |
12380 KB |
Output is correct |
8 |
Correct |
18 ms |
29788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4692 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6744 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6488 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6492 KB |
Output is correct |
10 |
Correct |
1 ms |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
7004 KB |
Output is correct |
12 |
Correct |
2 ms |
6748 KB |
Output is correct |
13 |
Correct |
1 ms |
6748 KB |
Output is correct |
14 |
Correct |
10 ms |
13784 KB |
Output is correct |
15 |
Correct |
9 ms |
12504 KB |
Output is correct |
16 |
Correct |
7 ms |
12380 KB |
Output is correct |
17 |
Correct |
7 ms |
12376 KB |
Output is correct |
18 |
Correct |
8 ms |
12216 KB |
Output is correct |
19 |
Correct |
3 ms |
10840 KB |
Output is correct |
20 |
Correct |
7 ms |
11612 KB |
Output is correct |
21 |
Correct |
11 ms |
14576 KB |
Output is correct |
22 |
Correct |
8 ms |
12504 KB |
Output is correct |
23 |
Correct |
8 ms |
12380 KB |
Output is correct |
24 |
Correct |
7 ms |
11100 KB |
Output is correct |
25 |
Correct |
1 ms |
4444 KB |
Output is correct |
26 |
Correct |
1 ms |
6748 KB |
Output is correct |
27 |
Correct |
1 ms |
4444 KB |
Output is correct |
28 |
Correct |
17 ms |
29788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
6492 KB |
Output is correct |
6 |
Correct |
1 ms |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
1 ms |
6492 KB |
Output is correct |
9 |
Correct |
1 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6748 KB |
Output is correct |
11 |
Correct |
1 ms |
7004 KB |
Output is correct |
12 |
Correct |
1 ms |
6748 KB |
Output is correct |
13 |
Correct |
1 ms |
6744 KB |
Output is correct |
14 |
Correct |
10 ms |
13692 KB |
Output is correct |
15 |
Correct |
9 ms |
12504 KB |
Output is correct |
16 |
Correct |
7 ms |
12380 KB |
Output is correct |
17 |
Correct |
7 ms |
12124 KB |
Output is correct |
18 |
Correct |
8 ms |
12216 KB |
Output is correct |
19 |
Correct |
3 ms |
10844 KB |
Output is correct |
20 |
Correct |
7 ms |
11520 KB |
Output is correct |
21 |
Correct |
12 ms |
14552 KB |
Output is correct |
22 |
Correct |
9 ms |
12544 KB |
Output is correct |
23 |
Correct |
8 ms |
12380 KB |
Output is correct |
24 |
Correct |
190 ms |
69352 KB |
Output is correct |
25 |
Correct |
151 ms |
39764 KB |
Output is correct |
26 |
Correct |
68 ms |
39080 KB |
Output is correct |
27 |
Correct |
176 ms |
55892 KB |
Output is correct |
28 |
Correct |
309 ms |
104376 KB |
Output is correct |
29 |
Correct |
253 ms |
74680 KB |
Output is correct |
30 |
Correct |
194 ms |
75704 KB |
Output is correct |
31 |
Correct |
9 ms |
11096 KB |
Output is correct |
32 |
Correct |
165 ms |
39564 KB |
Output is correct |
33 |
Correct |
1 ms |
4444 KB |
Output is correct |
34 |
Correct |
1 ms |
6748 KB |
Output is correct |
35 |
Correct |
124 ms |
55324 KB |
Output is correct |
36 |
Correct |
1 ms |
4440 KB |
Output is correct |
37 |
Correct |
18 ms |
29776 KB |
Output is correct |
38 |
Runtime error |
237 ms |
262144 KB |
Execution killed with signal 9 |
39 |
Halted |
0 ms |
0 KB |
- |