#include <bits/stdc++.h>
using namespace std;
#define sz(a) (int)a.size()
const int N = (int)1e3+10;
using ar = array<int,3>;
int X[] = {1,-1,0,0};
int Y[] = {0,0,1,-1};
string a[N];
bool vis[N][N];
int n, m, stX, stY, enX, enY;
pair<int,int> dr[4][N][N];
int D[N][N], sh[N][N];
priority_queue<ar,vector<ar>,greater<ar>> pq;
__attribute__((always_inline)) bool valid(int i, int j){
return i>=0 and j>=0 and i<n and j<m and a[i][j]!='#';
}
void dijkstra(int sti, int stj){
memset(D,63,sizeof(D));
pq.push({0,sti,stj}); D[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++){
auto [ni,nj] = dr[k][i][j];
if(valid(ni,nj) and D[ni][nj]>D[i][j]+sh[i][j])
D[ni][nj] = D[i][j]+sh[i][j], pq.push({D[ni][nj],ni,nj});
ni = i+X[k], nj = j+Y[k];
if(valid(ni,nj) and D[ni][nj]>D[i][j]+1)
D[ni][nj] = D[i][j]+1, pq.push({D[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;
}
int last = 0;
for(int j = 0; j < m; j++){
if(a[i][j]=='#') last = j+1;
else{
dr[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{
dr[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{
dr[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{
dr[3][i][j]={last,j};
sh[i][j]=min(sh[i][j],abs(last-i)+1);
}
}
}
dijkstra(stX,stY); cout << D[enX][enY];
}
Compilation message
portals.cpp: In function 'void dijkstra(int, int)':
portals.cpp:25:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
25 | if(vis[i][j]) continue; vis[i][j]=1;
| ^~
portals.cpp:25:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
25 | if(vis[i][j]) continue; vis[i][j]=1;
| ^~~
portals.cpp: At global scope:
portals.cpp:16:37: warning: 'always_inline' function might not be inlinable [-Wattributes]
16 | __attribute__((always_inline)) bool valid(int i, int j){
| ^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
8276 KB |
Output is correct |
2 |
Correct |
4 ms |
8404 KB |
Output is correct |
3 |
Correct |
4 ms |
8404 KB |
Output is correct |
4 |
Correct |
4 ms |
8404 KB |
Output is correct |
5 |
Correct |
3 ms |
8404 KB |
Output is correct |
6 |
Correct |
3 ms |
8404 KB |
Output is correct |
7 |
Correct |
4 ms |
8404 KB |
Output is correct |
8 |
Correct |
4 ms |
8404 KB |
Output is correct |
9 |
Correct |
4 ms |
8404 KB |
Output is correct |
10 |
Correct |
4 ms |
8276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
8276 KB |
Output is correct |
2 |
Correct |
3 ms |
8404 KB |
Output is correct |
3 |
Correct |
4 ms |
8496 KB |
Output is correct |
4 |
Correct |
4 ms |
8404 KB |
Output is correct |
5 |
Correct |
4 ms |
8404 KB |
Output is correct |
6 |
Correct |
3 ms |
8404 KB |
Output is correct |
7 |
Correct |
4 ms |
8404 KB |
Output is correct |
8 |
Correct |
3 ms |
8404 KB |
Output is correct |
9 |
Correct |
4 ms |
9172 KB |
Output is correct |
10 |
Correct |
4 ms |
9172 KB |
Output is correct |
11 |
Correct |
4 ms |
9172 KB |
Output is correct |
12 |
Correct |
5 ms |
9168 KB |
Output is correct |
13 |
Correct |
5 ms |
9172 KB |
Output is correct |
14 |
Correct |
4 ms |
8404 KB |
Output is correct |
15 |
Correct |
5 ms |
9172 KB |
Output is correct |
16 |
Correct |
4 ms |
8404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
8276 KB |
Output is correct |
2 |
Correct |
4 ms |
8404 KB |
Output is correct |
3 |
Correct |
4 ms |
8404 KB |
Output is correct |
4 |
Correct |
3 ms |
8404 KB |
Output is correct |
5 |
Correct |
10 ms |
13012 KB |
Output is correct |
6 |
Correct |
11 ms |
13032 KB |
Output is correct |
7 |
Correct |
12 ms |
13012 KB |
Output is correct |
8 |
Correct |
8 ms |
13012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
8276 KB |
Output is correct |
2 |
Correct |
4 ms |
8484 KB |
Output is correct |
3 |
Correct |
4 ms |
8404 KB |
Output is correct |
4 |
Correct |
3 ms |
8404 KB |
Output is correct |
5 |
Correct |
4 ms |
8404 KB |
Output is correct |
6 |
Correct |
4 ms |
8480 KB |
Output is correct |
7 |
Correct |
4 ms |
8404 KB |
Output is correct |
8 |
Correct |
4 ms |
8404 KB |
Output is correct |
9 |
Correct |
4 ms |
9172 KB |
Output is correct |
10 |
Correct |
4 ms |
9172 KB |
Output is correct |
11 |
Correct |
4 ms |
9168 KB |
Output is correct |
12 |
Correct |
4 ms |
9172 KB |
Output is correct |
13 |
Correct |
4 ms |
9200 KB |
Output is correct |
14 |
Correct |
10 ms |
12936 KB |
Output is correct |
15 |
Correct |
11 ms |
13012 KB |
Output is correct |
16 |
Correct |
12 ms |
13036 KB |
Output is correct |
17 |
Correct |
11 ms |
13012 KB |
Output is correct |
18 |
Correct |
12 ms |
13072 KB |
Output is correct |
19 |
Correct |
13 ms |
13036 KB |
Output is correct |
20 |
Correct |
13 ms |
13072 KB |
Output is correct |
21 |
Correct |
10 ms |
12980 KB |
Output is correct |
22 |
Correct |
11 ms |
13012 KB |
Output is correct |
23 |
Correct |
12 ms |
13032 KB |
Output is correct |
24 |
Correct |
12 ms |
13012 KB |
Output is correct |
25 |
Correct |
4 ms |
8404 KB |
Output is correct |
26 |
Correct |
4 ms |
9172 KB |
Output is correct |
27 |
Correct |
4 ms |
8404 KB |
Output is correct |
28 |
Correct |
7 ms |
13012 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
8284 KB |
Output is correct |
2 |
Correct |
4 ms |
8404 KB |
Output is correct |
3 |
Correct |
3 ms |
8404 KB |
Output is correct |
4 |
Correct |
4 ms |
8404 KB |
Output is correct |
5 |
Correct |
4 ms |
8452 KB |
Output is correct |
6 |
Correct |
4 ms |
8404 KB |
Output is correct |
7 |
Correct |
5 ms |
8404 KB |
Output is correct |
8 |
Correct |
3 ms |
8404 KB |
Output is correct |
9 |
Correct |
4 ms |
9172 KB |
Output is correct |
10 |
Correct |
5 ms |
9172 KB |
Output is correct |
11 |
Correct |
4 ms |
9172 KB |
Output is correct |
12 |
Correct |
4 ms |
9172 KB |
Output is correct |
13 |
Correct |
4 ms |
9300 KB |
Output is correct |
14 |
Correct |
10 ms |
13008 KB |
Output is correct |
15 |
Correct |
12 ms |
13012 KB |
Output is correct |
16 |
Correct |
12 ms |
13012 KB |
Output is correct |
17 |
Correct |
11 ms |
13012 KB |
Output is correct |
18 |
Correct |
13 ms |
13060 KB |
Output is correct |
19 |
Correct |
16 ms |
13012 KB |
Output is correct |
20 |
Correct |
13 ms |
13012 KB |
Output is correct |
21 |
Correct |
10 ms |
13012 KB |
Output is correct |
22 |
Correct |
10 ms |
12976 KB |
Output is correct |
23 |
Correct |
12 ms |
13012 KB |
Output is correct |
24 |
Correct |
202 ms |
42948 KB |
Output is correct |
25 |
Correct |
373 ms |
43040 KB |
Output is correct |
26 |
Correct |
273 ms |
42984 KB |
Output is correct |
27 |
Correct |
273 ms |
43000 KB |
Output is correct |
28 |
Correct |
148 ms |
42812 KB |
Output is correct |
29 |
Correct |
174 ms |
42708 KB |
Output is correct |
30 |
Correct |
204 ms |
42828 KB |
Output is correct |
31 |
Correct |
13 ms |
13012 KB |
Output is correct |
32 |
Correct |
245 ms |
42836 KB |
Output is correct |
33 |
Correct |
3 ms |
8404 KB |
Output is correct |
34 |
Correct |
5 ms |
9172 KB |
Output is correct |
35 |
Correct |
192 ms |
42916 KB |
Output is correct |
36 |
Correct |
4 ms |
8276 KB |
Output is correct |
37 |
Correct |
8 ms |
13012 KB |
Output is correct |
38 |
Correct |
99 ms |
42704 KB |
Output is correct |
39 |
Correct |
127 ms |
34892 KB |
Output is correct |