#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int maxn = 510, inf = 0x3f3f3f3f;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
typedef pair<int, int> ii;
int n, m, dist[maxn][maxn];
char mat[maxn][maxn];
ii pi, pf;
struct pos
{
int xi, xf, yi, yf;
} last[maxn][maxn];
struct iii
{
int d, x, y;
bool operator<(const iii& o) const
{
return d > o.d;
}
};
void dijkstra(ii x)
{
memset(dist, inf, sizeof dist);
priority_queue<iii> row;
dist[x.F][x.S] = 0;
row.push({0, x.F, x.S});
while(!row.empty())
{
int d = row.top().d;
int x = row.top().x;
int y = row.top().y;
row.pop();
if(d > dist[x][y]) continue;
int D = dist[x][y] + 1;
for(int i = 0 ; i < 4 ; ++i)
{
if(x + dx[i] <= n && x + dx[i] >= 1 && y + dy[i] >= 1 && y + dy[i] <= m && mat[x + dx[i]][y + dy[i]] != '#' && dist[x][y] + 1 < dist[x + dx[i]][y + dy[i]])
{
dist[x + dx[i]][y + dy[i]] = dist[x][y] + 1;
row.push({D, x + dx[i], y + dy[i]});
}
}
int xi = last[x][y].xi;
int xf = last[x][y].xf;
int yi = last[x][y].yi;
int yf = last[x][y].yf;
if(xi == y - 1)
{
if(xf != y + 1 && D < dist[x][xf-1])
{
dist[x][xf-1] = D;
row.push({D, x, xf-1});
}
if(yi != x - 1 && D < dist[yi+1][y])
{
dist[yi+1][y] = D;
row.push({D, yi+1, y});
}
if(yf != x + 1 && D < dist[yf-1][y])
{
dist[yf-1][y] = D;
row.push({D, yf-1, y});
}
}
if(xf == y + 1)
{
if(xi != y-1 && D < dist[x][xi+1])
{
dist[x][xi+1] = D;
row.push({D, x, xi+1});
}
if(yi != x - 1 && D < dist[yi+1][y])
{
dist[yi+1][y] = D;
row.push({D, yi+1, y});
}
if(yf != x + 1 && D < dist[yf-1][y])
{
dist[yf-1][y] = D;
row.push({D, yf-1, y});
}
}
if(yi == x-1)
{
if(xi != y-1 && D < dist[x][xi+1])
{
dist[x][xi+1] = D;
row.push({D, x, xi+1});
}
if(xf != y + 1 && D < dist[x][xf-1])
{
dist[x][xf-1] = D;
row.push({D, x, xf-1});
}
if(yf != x + 1 && D < dist[yf-1][y])
{
dist[yf-1][y] = D;
row.push({D, yf-1, y});
}
}
if(yf == x+1)
{
if(xi != y-1 && D < dist[x][xi+1])
{
dist[x][xi+1] = D;
row.push({D, x, xi+1});
}
if(xf != y + 1 && D < dist[x][xf-1])
{
dist[x][xf-1] = D;
row.push({D, x, xf-1});
}
if(yi != x - 1 && D < dist[yi+1][y])
{
dist[yi+1][y] = D;
row.push({D, yi+1, y});
}
}
}
}
int main()
{
cin >> n >> m;
memset(mat, '#', sizeof mat);
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= m ; ++j)
{
cin >> mat[i][j];
if(mat[i][j] == 'C') pi = {i, j};
if(mat[i][j] == 'F') pf = {i, j};
}
}
for(int i = 1 ; i <= n ; ++i)
{
int lasth = 0;
for(int j = 1 ; j <= m ; ++j)
{
if(mat[i][j] == '#') lasth = j;
else last[i][j].xi = lasth;
}
lasth = 0;
for(int j = m ; j >= 1 ; --j)
{
if(mat[i][j] == '#') lasth = j;
else last[i][j].xf = lasth;
}
}
for(int i = 1 ; i <= m ; ++i)
{
int lasth = 0;
for(int j = 1 ; j <= n ; ++j)
{
if(mat[j][i] == '#') lasth = j;
else last[j][i].yi = lasth;
}
lasth = 0;
for(int j = n ; j >= 1 ; --j)
{
if(mat[j][i] == '#') lasth = j;
else last[j][i].yf = lasth;
}
}
dijkstra(pi);
if(dist[pf.F][pf.S] == inf) cout << "nemoguce\n";
else cout << dist[pf.F][pf.S] << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1664 KB |
Output is correct |
2 |
Correct |
3 ms |
1664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1664 KB |
Output is correct |
2 |
Correct |
3 ms |
1664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1664 KB |
Output is correct |
2 |
Correct |
3 ms |
1664 KB |
Output is correct |
3 |
Correct |
3 ms |
1664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
2688 KB |
Output is correct |
2 |
Correct |
5 ms |
2304 KB |
Output is correct |
3 |
Correct |
6 ms |
2432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
2892 KB |
Output is correct |
2 |
Correct |
7 ms |
3200 KB |
Output is correct |
3 |
Correct |
8 ms |
2560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
4736 KB |
Output is correct |
2 |
Correct |
22 ms |
3584 KB |
Output is correct |
3 |
Correct |
15 ms |
3968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
41 ms |
5156 KB |
Output is correct |
2 |
Correct |
20 ms |
5504 KB |
Output is correct |
3 |
Correct |
23 ms |
3968 KB |
Output is correct |
4 |
Incorrect |
20 ms |
4736 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
47 ms |
5624 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |