#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(a) (int)a.size()
const int mxN = (int)1e3+10;
using ar = array<int,3>;
int X[] = {1,-1,0,0};
int Y[] = {0,0,1,-1};
string a[mxN];
bool vis[mxN][mxN];
int n, m, stX, stY, enX, enY;
pair<int,int> dir[4][mxN][mxN];
int dis[mxN][mxN], sh[mxN][mxN];
priority_queue<ar,vector<ar>,greater<ar>> pq;
bool valid(int i, int j){
return i>=0 and j>=0 and i<n and j<m and a[i][j]!='#';
}
void bfs(int sti, int stj){
memset(dis,63,sizeof(dis));
pq.push({0,sti,stj}); dis[sti][stj] = 0;
while(!pq.empty()){
auto [w,i,j] = pq.top(); pq.pop();
if(vis[i][j]) continue; vis[i][j]=1;
for(int k = 0; k < 4; k++){
int ni = i+X[k], nj = j+Y[k];
if(valid(ni,nj) and dis[ni][nj]>dis[i][j]+1)
dis[ni][nj] = dis[i][j]+1, pq.push({dis[ni][nj],ni,nj});
}
for(int k = 0; k < 4; k++){
auto [ni,nj] = dir[k][i][j];
if(valid(ni,nj) and dis[ni][nj]>dis[i][j]+sh[i][j])
dis[ni][nj] = dis[i][j]+sh[i][j], pq.push({dis[ni][nj],ni,nj});
}
}
}
int32_t main(){
cin >> n >> m; memset(sh,63,sizeof(sh));
for(int i = 0; i < n; i++){
cin >> a[i];
for(int j = 0; j < m; j++){
if(a[i][j]=='C') enX=i,enY=j;
else if(a[i][j]=='S') stX=i,stY=j;
}
}
for(int i = 0; i < n; i++){
int last = 0;
for(int j = 0; j < m; j++){
if(a[i][j]=='#') last = j+1;
else dir[0][i][j]={i,last},sh[i][j]=min(sh[i][j],abs(last-j)+1);
}
last = m-1;
for(int j = m-1; j >= 0; j--){
if(a[i][j]=='#') last = j-1;
else dir[1][i][j]={i,last},sh[i][j]=min(sh[i][j],abs(last-j)+1);
}
}
for(int j = 0; j < m; j++){
int last = 0;
for(int i = 0; i < n; i++){
if(a[i][j]=='#') last = i+1;
else dir[2][i][j]={last,j},sh[i][j]=min(sh[i][j],abs(last-i)+1);
}
last = n-1;
for(int i = n-1; i >= 0; i--){
if(a[i][j]=='#') last = i-1;
else dir[3][i][j]={last,j},sh[i][j]=min(sh[i][j],abs(last-i)+1);
}
}
bfs(stX,stY); cout << dis[enX][enY];
}
Compilation message
portals.cpp: In function 'void bfs(long long int, long long int)':
portals.cpp:27:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
27 | if(vis[i][j]) continue; vis[i][j]=1;
| ^~
portals.cpp:27:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
27 | if(vis[i][j]) continue; vis[i][j]=1;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
16340 KB |
Output is correct |
2 |
Correct |
9 ms |
16400 KB |
Output is correct |
3 |
Correct |
8 ms |
16408 KB |
Output is correct |
4 |
Correct |
7 ms |
16336 KB |
Output is correct |
5 |
Correct |
9 ms |
16468 KB |
Output is correct |
6 |
Correct |
8 ms |
16468 KB |
Output is correct |
7 |
Correct |
7 ms |
16468 KB |
Output is correct |
8 |
Correct |
7 ms |
16416 KB |
Output is correct |
9 |
Correct |
7 ms |
16340 KB |
Output is correct |
10 |
Correct |
7 ms |
16340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
16276 KB |
Output is correct |
2 |
Correct |
7 ms |
16468 KB |
Output is correct |
3 |
Correct |
7 ms |
16468 KB |
Output is correct |
4 |
Correct |
8 ms |
16340 KB |
Output is correct |
5 |
Correct |
9 ms |
16488 KB |
Output is correct |
6 |
Correct |
10 ms |
16416 KB |
Output is correct |
7 |
Correct |
9 ms |
16468 KB |
Output is correct |
8 |
Correct |
9 ms |
16600 KB |
Output is correct |
9 |
Correct |
11 ms |
17236 KB |
Output is correct |
10 |
Correct |
9 ms |
17328 KB |
Output is correct |
11 |
Correct |
10 ms |
17236 KB |
Output is correct |
12 |
Correct |
9 ms |
17232 KB |
Output is correct |
13 |
Correct |
8 ms |
17236 KB |
Output is correct |
14 |
Correct |
8 ms |
16340 KB |
Output is correct |
15 |
Correct |
8 ms |
17236 KB |
Output is correct |
16 |
Correct |
7 ms |
16376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
16340 KB |
Output is correct |
2 |
Correct |
11 ms |
16404 KB |
Output is correct |
3 |
Correct |
8 ms |
16468 KB |
Output is correct |
4 |
Correct |
8 ms |
16468 KB |
Output is correct |
5 |
Correct |
15 ms |
22288 KB |
Output is correct |
6 |
Correct |
15 ms |
22252 KB |
Output is correct |
7 |
Correct |
16 ms |
22324 KB |
Output is correct |
8 |
Correct |
12 ms |
22228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
16336 KB |
Output is correct |
2 |
Correct |
9 ms |
16472 KB |
Output is correct |
3 |
Correct |
6 ms |
16468 KB |
Output is correct |
4 |
Correct |
7 ms |
16340 KB |
Output is correct |
5 |
Correct |
7 ms |
16468 KB |
Output is correct |
6 |
Correct |
6 ms |
16468 KB |
Output is correct |
7 |
Correct |
6 ms |
16468 KB |
Output is correct |
8 |
Correct |
7 ms |
16468 KB |
Output is correct |
9 |
Correct |
7 ms |
17236 KB |
Output is correct |
10 |
Correct |
8 ms |
17348 KB |
Output is correct |
11 |
Correct |
7 ms |
17228 KB |
Output is correct |
12 |
Correct |
8 ms |
17236 KB |
Output is correct |
13 |
Correct |
8 ms |
17236 KB |
Output is correct |
14 |
Correct |
14 ms |
22228 KB |
Output is correct |
15 |
Correct |
16 ms |
22228 KB |
Output is correct |
16 |
Correct |
17 ms |
22328 KB |
Output is correct |
17 |
Correct |
17 ms |
22192 KB |
Output is correct |
18 |
Correct |
18 ms |
22264 KB |
Output is correct |
19 |
Correct |
18 ms |
22356 KB |
Output is correct |
20 |
Correct |
19 ms |
22356 KB |
Output is correct |
21 |
Correct |
15 ms |
22272 KB |
Output is correct |
22 |
Correct |
16 ms |
22248 KB |
Output is correct |
23 |
Correct |
16 ms |
22292 KB |
Output is correct |
24 |
Correct |
16 ms |
22228 KB |
Output is correct |
25 |
Correct |
7 ms |
16340 KB |
Output is correct |
26 |
Correct |
8 ms |
17256 KB |
Output is correct |
27 |
Correct |
8 ms |
16316 KB |
Output is correct |
28 |
Correct |
12 ms |
22228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
16340 KB |
Output is correct |
2 |
Correct |
7 ms |
16464 KB |
Output is correct |
3 |
Correct |
7 ms |
16468 KB |
Output is correct |
4 |
Correct |
7 ms |
16340 KB |
Output is correct |
5 |
Correct |
7 ms |
16464 KB |
Output is correct |
6 |
Correct |
8 ms |
16468 KB |
Output is correct |
7 |
Correct |
7 ms |
16468 KB |
Output is correct |
8 |
Correct |
8 ms |
16468 KB |
Output is correct |
9 |
Correct |
8 ms |
17236 KB |
Output is correct |
10 |
Correct |
8 ms |
17232 KB |
Output is correct |
11 |
Correct |
9 ms |
17296 KB |
Output is correct |
12 |
Correct |
8 ms |
17312 KB |
Output is correct |
13 |
Correct |
8 ms |
17340 KB |
Output is correct |
14 |
Correct |
14 ms |
22192 KB |
Output is correct |
15 |
Correct |
16 ms |
22244 KB |
Output is correct |
16 |
Correct |
18 ms |
22228 KB |
Output is correct |
17 |
Correct |
14 ms |
22276 KB |
Output is correct |
18 |
Correct |
18 ms |
22356 KB |
Output is correct |
19 |
Correct |
18 ms |
22364 KB |
Output is correct |
20 |
Correct |
19 ms |
22356 KB |
Output is correct |
21 |
Correct |
14 ms |
22236 KB |
Output is correct |
22 |
Correct |
16 ms |
22176 KB |
Output is correct |
23 |
Correct |
15 ms |
22236 KB |
Output is correct |
24 |
Correct |
232 ms |
83696 KB |
Output is correct |
25 |
Correct |
405 ms |
83848 KB |
Output is correct |
26 |
Correct |
317 ms |
83640 KB |
Output is correct |
27 |
Correct |
296 ms |
83708 KB |
Output is correct |
28 |
Correct |
178 ms |
83308 KB |
Output is correct |
29 |
Correct |
197 ms |
83420 KB |
Output is correct |
30 |
Correct |
228 ms |
83348 KB |
Output is correct |
31 |
Correct |
17 ms |
22228 KB |
Output is correct |
32 |
Correct |
300 ms |
83512 KB |
Output is correct |
33 |
Correct |
7 ms |
16340 KB |
Output is correct |
34 |
Correct |
8 ms |
17236 KB |
Output is correct |
35 |
Correct |
221 ms |
75688 KB |
Output is correct |
36 |
Correct |
7 ms |
16340 KB |
Output is correct |
37 |
Correct |
13 ms |
22232 KB |
Output is correct |
38 |
Correct |
135 ms |
83396 KB |
Output is correct |
39 |
Correct |
148 ms |
60008 KB |
Output is correct |