#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
const ll maxn=1005;
char grid[maxn][maxn];
ll dis[maxn][maxn];
ii wall[maxn][maxn][4]; //N,E,S,W
ll hasWall[maxn][maxn];
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll r,c;
ii s,e;
cin>>r>>c;
for (int i=0;i<=r+1;i++){
for (int j=0;j<=c+1;j++){
grid[i][j]='#';
}
}
for (int i=1;i<=r;i++){
for (int j=1;j<=c;j++){
cin>>grid[i][j];
if (grid[i][j]=='S') s={i,j};
if (grid[i][j]=='C') e={i,j};
}
}
memset(dis,63,sizeof(dis));
memset(hasWall,63,sizeof(hasWall));
for (int i=1;i<=r;i++){
ii p={0,0};
ll cnt=0;
for (int j=0;j<=c+1;j++){
if (grid[i][j]=='#')
p={i,j+1},cnt=0;
else{
wall[i][j][0]=p;
cnt++;
hasWall[i][j]=min(hasWall[i][j],cnt);
}
//first open square
}
}
for (int i=1;i<=c;i++){
ii p={0,0};
ll cnt=0;
for (int j=0;j<=r+1;j++){
if (grid[j][i]=='#'){
p={j+1,i},cnt=0;
}
else{
cnt++;
wall[j][i][1]=p;
hasWall[j][i]=min(hasWall[j][i],cnt);
}
}
}
for (int i=1;i<=r;i++){
ii p={0,0};
ll cnt=0;
for (int j=c+1;j>=0;j--){
if (grid[i][j]=='#')
p={i,j-1}, cnt=0;
else{
cnt++;
wall[i][j][2]=p;
hasWall[i][j]=min(hasWall[i][j],cnt);
}
}
}
for (int i=1;i<=c;i++){
ii p={0,0};
ll cnt=0;
for (int j=r+1;j>=0;j--){
if (grid[j][i]=='#'){
p={j-1,i};
cnt=0;
}
else{
cnt++;
wall[j][i][3]=p;
hasWall[j][i]=min(hasWall[j][i],cnt);
}
}
}
priority_queue<pair<ll,ii>,vector<pair<ll,ii>>,greater<pair<ll,ii>>> pq;
pq.emplace(0,make_pair(s.first,s.second));
while (pq.size()){
ll d,x,y;
ii p;
tie(d,p)=pq.top();
tie(x,y)=p;
pq.pop();
//cerr<<d<<' '<<x<<' '<<y<<endl;
if (dis[x][y]<=d) continue;
dis[x][y]=d;
for (int i=0;i<4;i++){
ll nx=wall[x][y][i].first,ny=wall[x][y][i].second;
if (dis[nx][ny]<=d+hasWall[x][y]) continue;
pq.emplace(d+hasWall[x][y],make_pair(nx,ny));
}
for (int i=0;i<4;i++){
ll nx=x+dx[i],ny=y+dy[i];
if (grid[nx][ny]=='#') continue;
if (dis[nx][ny]<=d+1) continue;
pq.emplace(d+1,make_pair(nx,ny));
}
}
cout<<dis[e.first][e.second];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18008 KB |
Output is correct |
2 |
Correct |
3 ms |
19804 KB |
Output is correct |
3 |
Correct |
3 ms |
19800 KB |
Output is correct |
4 |
Correct |
3 ms |
17756 KB |
Output is correct |
5 |
Correct |
3 ms |
19804 KB |
Output is correct |
6 |
Correct |
3 ms |
19804 KB |
Output is correct |
7 |
Correct |
3 ms |
19804 KB |
Output is correct |
8 |
Correct |
3 ms |
19804 KB |
Output is correct |
9 |
Correct |
3 ms |
17756 KB |
Output is correct |
10 |
Correct |
3 ms |
17756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
17756 KB |
Output is correct |
2 |
Correct |
3 ms |
19836 KB |
Output is correct |
3 |
Correct |
3 ms |
19804 KB |
Output is correct |
4 |
Correct |
3 ms |
17756 KB |
Output is correct |
5 |
Correct |
3 ms |
20056 KB |
Output is correct |
6 |
Correct |
3 ms |
19804 KB |
Output is correct |
7 |
Correct |
3 ms |
19804 KB |
Output is correct |
8 |
Correct |
3 ms |
19804 KB |
Output is correct |
9 |
Correct |
4 ms |
22108 KB |
Output is correct |
10 |
Correct |
5 ms |
22364 KB |
Output is correct |
11 |
Correct |
4 ms |
22108 KB |
Output is correct |
12 |
Correct |
4 ms |
22108 KB |
Output is correct |
13 |
Correct |
4 ms |
21936 KB |
Output is correct |
14 |
Correct |
3 ms |
17756 KB |
Output is correct |
15 |
Correct |
4 ms |
22108 KB |
Output is correct |
16 |
Correct |
3 ms |
17756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
18008 KB |
Output is correct |
2 |
Correct |
3 ms |
19804 KB |
Output is correct |
3 |
Correct |
3 ms |
19804 KB |
Output is correct |
4 |
Correct |
3 ms |
20028 KB |
Output is correct |
5 |
Correct |
11 ms |
30296 KB |
Output is correct |
6 |
Correct |
11 ms |
30300 KB |
Output is correct |
7 |
Correct |
15 ms |
30652 KB |
Output is correct |
8 |
Correct |
7 ms |
30300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
17752 KB |
Output is correct |
2 |
Correct |
3 ms |
19804 KB |
Output is correct |
3 |
Correct |
3 ms |
19804 KB |
Output is correct |
4 |
Correct |
3 ms |
17756 KB |
Output is correct |
5 |
Correct |
3 ms |
19800 KB |
Output is correct |
6 |
Correct |
4 ms |
19920 KB |
Output is correct |
7 |
Correct |
4 ms |
19804 KB |
Output is correct |
8 |
Correct |
3 ms |
19804 KB |
Output is correct |
9 |
Correct |
4 ms |
22108 KB |
Output is correct |
10 |
Correct |
5 ms |
22364 KB |
Output is correct |
11 |
Correct |
4 ms |
22108 KB |
Output is correct |
12 |
Correct |
4 ms |
22108 KB |
Output is correct |
13 |
Correct |
4 ms |
22108 KB |
Output is correct |
14 |
Correct |
9 ms |
30296 KB |
Output is correct |
15 |
Correct |
11 ms |
30540 KB |
Output is correct |
16 |
Correct |
12 ms |
30556 KB |
Output is correct |
17 |
Correct |
15 ms |
30556 KB |
Output is correct |
18 |
Correct |
17 ms |
30488 KB |
Output is correct |
19 |
Correct |
20 ms |
30808 KB |
Output is correct |
20 |
Correct |
34 ms |
35028 KB |
Output is correct |
21 |
Correct |
9 ms |
30300 KB |
Output is correct |
22 |
Correct |
10 ms |
30496 KB |
Output is correct |
23 |
Correct |
11 ms |
30300 KB |
Output is correct |
24 |
Correct |
14 ms |
30556 KB |
Output is correct |
25 |
Correct |
3 ms |
17756 KB |
Output is correct |
26 |
Correct |
4 ms |
22108 KB |
Output is correct |
27 |
Correct |
3 ms |
17756 KB |
Output is correct |
28 |
Correct |
6 ms |
30300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
17752 KB |
Output is correct |
2 |
Correct |
3 ms |
19804 KB |
Output is correct |
3 |
Correct |
3 ms |
19800 KB |
Output is correct |
4 |
Correct |
3 ms |
17756 KB |
Output is correct |
5 |
Correct |
3 ms |
19924 KB |
Output is correct |
6 |
Correct |
3 ms |
19804 KB |
Output is correct |
7 |
Correct |
3 ms |
19804 KB |
Output is correct |
8 |
Correct |
3 ms |
20056 KB |
Output is correct |
9 |
Correct |
4 ms |
22108 KB |
Output is correct |
10 |
Correct |
5 ms |
22224 KB |
Output is correct |
11 |
Correct |
4 ms |
22104 KB |
Output is correct |
12 |
Correct |
4 ms |
22108 KB |
Output is correct |
13 |
Correct |
4 ms |
22108 KB |
Output is correct |
14 |
Correct |
10 ms |
30396 KB |
Output is correct |
15 |
Correct |
11 ms |
30532 KB |
Output is correct |
16 |
Correct |
13 ms |
30296 KB |
Output is correct |
17 |
Correct |
13 ms |
30552 KB |
Output is correct |
18 |
Correct |
17 ms |
30556 KB |
Output is correct |
19 |
Correct |
20 ms |
30724 KB |
Output is correct |
20 |
Correct |
33 ms |
34256 KB |
Output is correct |
21 |
Correct |
9 ms |
30296 KB |
Output is correct |
22 |
Correct |
10 ms |
30296 KB |
Output is correct |
23 |
Correct |
11 ms |
30300 KB |
Output is correct |
24 |
Correct |
334 ms |
81832 KB |
Output is correct |
25 |
Correct |
443 ms |
83144 KB |
Output is correct |
26 |
Correct |
698 ms |
95416 KB |
Output is correct |
27 |
Execution timed out |
1069 ms |
130960 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |