제출 #72418

#제출 시각아이디문제언어결과실행 시간메모리
72418동진의 (#118)수중 미로 (FXCUP3_aqua)C++17
0 / 100
24 ms25828 KiB
#include <stdio.h> #include <string.h> #include <queue> #include <vector> using namespace std; struct point { int y, x, cost; }; queue<point> q; vector<point> graph[902][902]; char map[902][902]; int visited[902][902]; int dy[4] = { 1, -1, 0, 0 }; int dx[4] = { 0, 0, 1, -1 }; int dp[902][902]; int inq[902][902]; void bfs(int y, int x) { q.push({ y, x, 0 }); visited[y][x] = 1; while (!q.empty()) { point cur = q.front(); q.pop(); for (int i = 0; i < 4; i++) { point next = { cur.y + dy[i], cur.x + dx[i], cur.cost + 1 }; int bo = 0; int cnt = 0; while (i < 2 && map[next.y][next.x] != 0) { if (visited[next.y][next.x] == 0 && bo == 2 && map[next.y][next.x] == 'W') break; if (visited[next.y][next.x] == 0 && bo <= 1 && map[next.y][next.x] == 'W') { bo = 1; cnt++; } if (visited[next.y][next.x] == 0 && bo >= 1 && map[next.y][next.x] == '.') { visited[next.y][next.x] = 1; graph[cur.y][cur.x].push_back({ next.y, next.x, cnt * cnt }); q.push(next); bo = 2; } next.y += dy[i]; } while (i >= 2 && map[next.y][next.x] != 0) { if (visited[next.y][next.x] == 0 && bo == 2 && map[next.y][next.x] == 'W') break; if (visited[next.y][next.x] == 0 && bo <= 1 && map[next.y][next.x] == 'W') { bo = 1; cnt++; } if (visited[next.y][next.x] == 0 && bo >= 1 && map[next.y][next.x] != 'W') { visited[next.y][next.x] = 1; graph[cur.y][cur.x].push_back({ next.y, next.x, cnt * cnt }); q.push(next); bo = 2; } next.x += dx[i]; } } } } void spfa(int y, int x) { dp[y][x] = 0; q.push({ y, x, 0 }); inq[y][x] = 1; while (!q.empty()) { point cur = q.front(); q.pop(); inq[cur.y][cur.x] = 0; //printf("debug : %d %d\n", cur.y, cur.x); for (int i = 0; i < graph[cur.y][cur.x].size(); i++) { point next = graph[cur.y][cur.x][i]; if (dp[next.y][next.x] > dp[cur.y][cur.x] + next.cost) { dp[next.y][next.x] = dp[cur.y][cur.x] + next.cost; if (inq[next.y][next.x] == 0) q.push(next); } } } } int main() { int n; int mY, mX; int hY, hX; scanf(" %d", &n); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf(" %c", &map[i][j]); if (map[i][j] == 'M') { mY = i; mX = j; } else if (map[i][j] == 'H') { hY = i; hX = j; } } } bfs(mY, mX); memset(visited, 0, sizeof(visited)); memset(dp, 50, sizeof(dp)); spfa(mY, mX); if (dp[hY][hX] < 10000000) printf("%d\n", dp[hY][hX]); else printf("-1\n"); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

aqua.cpp: In function 'void spfa(int, int)':
aqua.cpp:87:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < graph[cur.y][cur.x].size(); i++)
                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua.cpp: In function 'int main()':
aqua.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d", &n);
  ~~~~~^~~~~~~~~~~
aqua.cpp:111:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &map[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~
aqua.cpp:129:15: warning: 'hX' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (dp[hY][hX] < 10000000)
      ~~~~~~~~~^
aqua.cpp:129:15: warning: 'hY' may be used uninitialized in this function [-Wmaybe-uninitialized]
aqua.cpp:128:6: warning: 'mX' may be used uninitialized in this function [-Wmaybe-uninitialized]
  spfa(mY, mX);
  ~~~~^~~~~~~~
aqua.cpp:128:6: warning: 'mY' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...