#include <bits/stdc++.h>
#define N 1050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;
int n, m, xo, yo, xi, yi, dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
int id[N][N], cnt, dist[N*N], pai[N*N];
pii O[N];
char mat[N][N];
vector<pii> grafo[N*N];
inline int solve(int ini, int fim)
{
priority_queue<pii, vector<pii>, greater<pii> > fila;
memset(dist, 0x3f3f3f3f, sizeof dist);
dist[ini] = 0;
fila.push({0, ini});
while(!fila.empty())
{
int x = fila.top().s, d = fila.top().s;
fila.pop();
if(d > dist[x]) continue;
for(auto v: grafo[x])
{
if(dist[v.f] > dist[x] + v.s)
{
dist[v.f] = dist[x] + v.s;
pai[v.f] = x;
fila.push({dist[v.f], v.f});
}
}
}
int u = fim;
return dist[fim];
}
pii esq[N][N], dir[N][N], baixo[N][N], cima[N][N];
inline void fill()
{
for(int i = 1; i <= n; i++)
{
int ultimo = 0;
for(int j = 1; j <= m; j++)
{
if(mat[i][j] == '#') ultimo = j;
esq[i][j] = {i, ultimo + 1};
}
ultimo = m + 1;
for(int j = m; j >= 1; j--)
{
if(mat[i][j] == '#') ultimo = j;
dir[i][j] = {i, ultimo - 1};
}
}
for(int j = 1; j <= m; j++)
{
int ultimo = 0;
for(int i = 1; i <= n; i++)
{
if(mat[i][j] == '#') ultimo = i;
cima[i][j] = {ultimo + 1, j};
}
ultimo = n + 1;
for(int i = n; i >= 1; i --)
{
if(mat[i][j] == '#') ultimo = i;
baixo[i][j] = {ultimo - 1, j};
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int i = 0; i <= n + 1; i++)
{
for(int j = 0; j <= m + 1; j++)
{
id[i][j] = ++ cnt;
O[id[i][j]] = {i, j};
}
}
for(int i = 0; i <= n + 1; i++)
for(int j = 0; j <= m + 1; j++)
{
if(!i or i == n + 1 or !j or j == m + 1)
{
mat[i][j] = '#';
continue;
}
cin>>mat[i][j];
if(mat[i][j] == 'S') xo = i, yo = j;
if(mat[i][j] == 'C') xi = i, yi = j;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
int x = id[i][j];
if(mat[i][j] != '#')
{
for(int p = 0; p < 4; p++)
{
int a = i + dx[p], b = j + dy[p];
if(a < 0 or b < 0 or a > n + 1 or b > m + 1) continue;
if(mat[a][b] != '#') grafo[x].push_back({id[a][b], 1});
}
}
}
}
fill();
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(mat[i][j] == '#') continue;
vector< pii > pos;
pos.push_back(esq[i][j]), pos.push_back(dir[i][j]);
pos.push_back(baixo[i][j]), pos.push_back(cima[i][j]);
int x = id[i][j], custo = 2000000000;
for(int a = 0; a < pos.size(); a++)
{
int A = abs(i - pos[a].f) + abs(j - pos[a].s);
custo = min(custo, A + 1);
}
for(int a = 0; a < pos.size(); a++) grafo[x].push_back({id[pos[a].f][pos[a].s], custo});
}
}
cout<<solve(id[xo][yo], id[xi][yi])<<"\n";
}
Compilation message
portals.cpp: In function 'int solve(int, int)':
portals.cpp:49:6: warning: unused variable 'u' [-Wunused-variable]
int u = fim;
^
portals.cpp: In function 'int main()':
portals.cpp:170:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a = 0; a < pos.size(); a++)
~~^~~~~~~~~~~~
portals.cpp:177:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a = 0; a < pos.size(); a++) grafo[x].push_back({id[pos[a].f][pos[a].s], custo});
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
30584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
30696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
30696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
30712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
30724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
