#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;
int X[] = {1,-1,0,0};
int Y[] = {0,0,1,-1};
int n, m, stX, stY, enX, enY;
string a[mxN];
queue<pair<int,int>> Q;
int dis[mxN][mxN];
pair<int,int> dir[4][mxN][mxN];
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 i, int j){
memset(dis,-1,sizeof(dis));
Q.push({i,j}); dis[i][j] = 0;
while(!Q.empty()){
auto [i,j] = Q.front();
bool ok = 0; Q.pop();
for(int k = 0; k < 4; k++){
int ni = i+X[k], nj = j+Y[k];
if(valid(ni,nj) and dis[ni][nj]==-1)
dis[ni][nj] = dis[i][j]+1, Q.push({ni,nj});
else if(!valid(ni,nj)) ok=1;
}
for(int k = 0; k < 4 and ok; k++){
auto [ni,nj] = dir[k][i][j];
if(valid(ni,nj) and dis[ni][nj]==-1)
dis[ni][nj] = dis[i][j]+1, Q.push({ni,nj});
}
}
}
int32_t main(){
cin >> n >> m;
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};
}
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};
}
}
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};
}
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};
}
}
bfs(stX,stY); cout << dis[enX][enY];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8296 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 |
4 ms |
8408 KB |
Output is correct |
6 |
Correct |
4 ms |
8404 KB |
Output is correct |
7 |
Correct |
3 ms |
8404 KB |
Output is correct |
8 |
Correct |
4 ms |
8404 KB |
Output is correct |
9 |
Correct |
3 ms |
8404 KB |
Output is correct |
10 |
Incorrect |
4 ms |
8404 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8276 KB |
Output is correct |
2 |
Correct |
3 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 |
8404 KB |
Output is correct |
6 |
Correct |
4 ms |
8404 KB |
Output is correct |
7 |
Correct |
3 ms |
8496 KB |
Output is correct |
8 |
Correct |
4 ms |
8408 KB |
Output is correct |
9 |
Correct |
4 ms |
9300 KB |
Output is correct |
10 |
Incorrect |
4 ms |
9172 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8276 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 |
10 ms |
14220 KB |
Output is correct |
6 |
Correct |
10 ms |
14036 KB |
Output is correct |
7 |
Correct |
9 ms |
14036 KB |
Output is correct |
8 |
Correct |
8 ms |
14036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8276 KB |
Output is correct |
2 |
Correct |
3 ms |
8404 KB |
Output is correct |
3 |
Correct |
4 ms |
8404 KB |
Output is correct |
4 |
Correct |
5 ms |
8412 KB |
Output is correct |
5 |
Correct |
4 ms |
8404 KB |
Output is correct |
6 |
Correct |
4 ms |
8404 KB |
Output is correct |
7 |
Correct |
4 ms |
8404 KB |
Output is correct |
8 |
Correct |
4 ms |
8532 KB |
Output is correct |
9 |
Correct |
4 ms |
9172 KB |
Output is correct |
10 |
Incorrect |
4 ms |
9300 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
8276 KB |
Output is correct |
2 |
Correct |
5 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 |
4 ms |
8404 KB |
Output is correct |
6 |
Correct |
4 ms |
8404 KB |
Output is correct |
7 |
Correct |
4 ms |
8404 KB |
Output is correct |
8 |
Correct |
3 ms |
8484 KB |
Output is correct |
9 |
Correct |
5 ms |
9300 KB |
Output is correct |
10 |
Incorrect |
4 ms |
9172 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |