#include <bits/stdc++.h>
using namespace std;
int R, C, i, j;
char lab[1005][1005];
int wx[1005][1005][2], wy[1005][1005][2];
int t[1005][1005];
int cx, cy;
queue< pair<int, int> > q;
void bfs(int x, int y)
{
if (x >= 0 && y >= 0 && x < C && y < R && t[y][x] == -1 && lab[y][x] != '#')
{
t[y][x] = t[j][i] + 1;
q.push(make_pair(x, y));
}
}
int main()
{
cin >> R >> C;
for(int j = 0; j < R; j++)
{
for(int i = 0; i < C; i++) cin >> lab[j][i];
for(int i = 0; i < C; i++)
{
t[j][i] = -1;
if(lab[j][i] == 'S') {t[j][i] = 0; q.push(make_pair(i, j));}
if(lab[j][i] == 'C') {cx = i; cy = j;}
}
}
for(int j = 0; j < R; j++)
for(int i = 0; i < C; i++)
{
wy[j][i][0] = (j == 0 || lab[j-1][i] == '#') ? j : wy[j-1][i][0];
wx[j][i][0] = (i == 0 || lab[j][i-1] == '#') ? i : wx[j][i-1][0];
}
for(int j = R-1; j >= 0; j--)
for(int i = C-1; i >= 0; i--)
{
wy[j][i][1] = (j == R-1 || lab[j+1][i] == '#') ? j : wy[j+1][i][1];
wx[j][i][1] = (i == C-1 || lab[j][i+1] == '#') ? i : wx[j][i+1][1];
}
while (q.size() && t[cy][cx] == -1)
{
i = q.front().first;
j = q.front().second;
q.pop();
bfs(i, j-1);
bfs(i, j+1);
bfs(i-1, j);
bfs(i+1, j);
if (wx[j][i][0] == i || wx[j][i][1] == i || wy[j][i][0] == j || wy[j][i][1] == j)
{
bfs(wx[j][i][0], j);
bfs(wx[j][i][1], j);
bfs(i, wy[j][i][0]);
bfs(i, wy[j][i][1]);
}
}
cout << t[cy][cx];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
6 ms |
3412 KB |
Output is correct |
6 |
Correct |
6 ms |
3412 KB |
Output is correct |
7 |
Correct |
5 ms |
3412 KB |
Output is correct |
8 |
Correct |
5 ms |
3412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
980 KB |
Output is correct |
10 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |