이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define pli pair<long long,int>
using namespace std;
int n, Num[910][910], NX[910][910], NY[910][910], BX[910], EX[910], BY[910], EY[910];
int L[3010000];
long long D[3010000];
char p[910][910];
priority_queue<pli>PQ;
vector<int>E[3010000], LL[3010000];
void Add_Edge(int a, int b, int d) {
E[a].push_back(b);
LL[a].push_back(d*d);
}
void Put(int a, long long d) {
if (D[a] <= d)return;
D[a] = d;
PQ.push({ -d,a });
}
int main() {
//freopen("input.txt", "r", stdin);
int i, j, sx, sy, cnt = 0, ex, ey;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%s", p[i]+1);
for (j = 1; j <= n; j++){
if (p[i][j] == 'M') {
sx = i, sy = j;
p[i][j] = '.';
}
if (p[i][j] == 'H') {
ex = i, ey = j;
p[i][j] = '.';
}
if (p[i][j] == '.') {
cnt++;
Num[i][j] = cnt;
}
}
}
for (i = 1; i <= n; i++) {
BX[i] = cnt + 1;
int c = 0, cp = 0;
for (j = 1; j <= n; j++) {
if (p[i][j] == '.') {
if (p[i][j - 1] != '.')cnt++;
if (c) {
cp = c;
c = 0;
L[cnt] = cp;
}
NX[i][j] = cnt;
}
if (p[i][j] == 'W') {
c++;
}
}
EX[i] = cnt;
}
for (i = 1; i <= n; i++) {
BY[i] = cnt + 1;
int c = 0, cp = 0;
for (j = 1; j <= n; j++) {
if (p[j][i] == '.') {
if (p[j - 1][i] != '.')cnt++;
if (c) {
cp = c;
c = 0;
L[cnt] = cp;
}
NY[j][i] = cnt;
}
if (p[j][i] == 'W') {
c++;
}
}
EY[i] = cnt;
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
Add_Edge(NX[i][j], Num[i][j], 0);
Add_Edge(NY[i][j], Num[i][j], 0);
if (NX[i][j] != BX[i]) {
Add_Edge(Num[i][j], NX[i][j] - 1, L[NX[i][j]]);
}
if (NX[i][j] != EX[i]) {
Add_Edge(Num[i][j], NX[i][j] + 1, L[NX[i][j] + 1]);
}
if (NY[i][j] != BY[j]) {
Add_Edge(Num[i][j], NY[i][j] - 1, L[NY[i][j]]);
}
if (NY[i][j] != EY[j]) {
Add_Edge(Num[i][j], NY[i][j] + 1, L[NY[i][j] + 1]);
}
}
}
for (i = 1; i <= cnt; i++)D[i] = 1e18;
Put(Num[sx][sy], 0);
while (!PQ.empty()) {
pli tp = PQ.top();
PQ.pop();
int x = tp.second;
if (D[x] != -tp.first)continue;
for (i = 0; i < E[x].size(); i++) {
Put(E[x][i], D[x] + LL[x][i]);
}
}
long long res = D[Num[ex][ey]];
if (res > 8e16)res = -1;
printf("%lld\n", res);
}
컴파일 시 표준 에러 (stderr) 메시지
aqua.cpp: In function 'int main()':
aqua.cpp:106:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < E[x].size(); i++) {
~~^~~~~~~~~~~~~
aqua.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
aqua.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", p[i]+1);
~~~~~^~~~~~~~~~~~~~
aqua.cpp:100:5: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
Put(Num[sx][sy], 0);
~~~^~~~~~~~~~~~~~~~
aqua.cpp:100:5: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
aqua.cpp:110:30: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
long long res = D[Num[ex][ey]];
~~~~~~~~~~^
aqua.cpp:110:30: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |