이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<string> s(n + 2, string(m + 2, '#'));
for (int i = 1; i <= n; i++)
{
string t;
cin >> t;
t = "#" + t + "#";
s[i] = t;
}
n += 2, m += 2;
vector<vector<int> > up(n, vector<int>(m));
for (int i = 1; i < n; i++)
{
for (int j = 0; j < m; j++)
{
up[i][j] = up[i - 1][j];
if (s[i - 1][j] == '#')
up[i][j] = i;
}
}
vector<vector<int> > down(n, vector<int>(m));
for (int i = n - 2; i >= 0; i--)
{
for (int j = 0; j < m; j++)
{
down[i][j] = down[i + 1][j];
if (s[i + 1][j] == '#')
down[i][j] = i;
}
}
vector<vector<int> > right(n, vector<int>(m));
vector<vector<int> > left(n, vector<int>(m));
for (int i = 0; i < n; i++)
{
for (int j = 1; j < m; j++)
{
left[i][j] = left[i][j - 1];
if (s[i][j - 1] == '#')
left[i][j] = j;
}
}
for (int i = 0; i < n; i++)
{
for (int j = m - 2; j >= 0; j--)
{
right[i][j] = right[i][j + 1];
if (s[i][j + 1] == '#')
right[i][j] = j;
}
}
vector<int> cx = {0, 0, -1, 1};
vector<int> cy = {1, -1, 0, 0};
int sx, sy, fx, fy;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (s[i][j] == 'S') sx = i, sy = j;
if (s[i][j] == 'C') fx = i, fy = j;
}
}
const int INF = 1e9;
vector<vector<int> > dist(n, vector<int>(m, INF));
dist[sx][sy] = 0;
vector<pair<int, int> > q = {{sx, sy}};
for (int i = 0; i < q.size(); i++)
{
int x = q[i].first, y = q[i].second;
//cout << x << " " << y << endl;
//cout << s[x][y] << endl;
for (int k = 0; k < 4; k++)
{
int nx = x + cx[k], ny = y + cy[k];
if (s[nx][ny] != '#' && dist[nx][ny] > dist[x][y] + 1)
{
dist[nx][ny] = dist[x][y] + 1;
q.push_back({nx, ny});
}
}
{
int nx = x, ny = left[x][y];
if (dist[nx][ny] > dist[x][y] + 1)
{
dist[nx][ny] = dist[x][y] + 1;
q.push_back({nx, ny});
}
}
{
int nx = x, ny = right[x][y];
if (dist[nx][ny] > dist[x][y] + 1)
{
dist[nx][ny] = dist[x][y] + 1;
q.push_back({nx, ny});
}
}
{
int nx = up[x][y], ny = y;
if (dist[nx][ny] > dist[x][y] + 1)
{
dist[nx][ny] = dist[x][y] + 1;
q.push_back({nx, ny});
}
}
{
int nx = down[x][y], ny = y;
if (dist[nx][ny] > dist[x][y] + 1)
{
dist[nx][ny] = dist[x][y] + 1;
q.push_back({nx, ny});
}
}
}
cout << dist[fx][fy];
}
컴파일 시 표준 에러 (stderr) 메시지
portals.cpp: In function 'int main()':
portals.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 0; i < q.size(); i++)
| ~~^~~~~~~~~~
portals.cpp:64:13: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
64 | int sx, sy, fx, fy;
| ^~
portals.cpp:64:9: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
64 | int sx, sy, fx, fy;
| ^~
portals.cpp:124:24: warning: 'fy' may be used uninitialized in this function [-Wmaybe-uninitialized]
124 | cout << dist[fx][fy];
| ^
portals.cpp:124:20: warning: 'fx' may be used uninitialized in this function [-Wmaybe-uninitialized]
124 | cout << dist[fx][fy];
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |