# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
72272 | 2018-08-26T06:39:57 Z | 동진의 (#2167, kdk3776, define_chan, Jinpari) | Aquatic Labyrinth (FXCUP3_aqua) | C++17 | 2 ms | 356 KB |
#include<iostream> #include<cmath> #include<cstring> #include<queue> #include<stack> #include<list> #include<cstring> #include<algorithm> #define fio ios_base::sync_with_stdio(0) //배열크기 확인 #define MAXNUM 20 using namespace std; struct point{ int x, y, cost; point operator +(const point & a) const{ return {x + a.x, y + a.y, cost}; } }; int main(){ int n; int ans=1000000000; int cost[MAXNUM][MAXNUM]={0}; char map[MAXNUM][MAXNUM]={0}; queue<point> q; memset(cost, 40, sizeof(cost)); point dir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; scanf("%d", &n); for (int i=1; i<=n; i++) scanf("%s", map[i]+1); for (int i=0; i<=n+1; i++) {map[i][0] = map[i][n+1] = map[0][i] = map[n+1][i] = '#';} for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { if (map[i][j] == 'M') { q.push({j, i, 0}); cost[i][j] = 0; } } } while (!q.empty()) { point cur = q.front(); q.pop(); for (int i=0; i<4; i++) { int cnt=0; point next = cur; while (map[next.y][next.x] != 'W' && map[next.y][next.x] != '#') { if (map[next.y][next.x] == 'H') { ans = min(ans, cur.cost); } next = next + dir[i]; } while (map[next.y][next.x] == 'W') { cnt++; next = next + dir[i]; } next.cost += cnt * cnt; if (map[next.y][next.x] == '.' || map[next.y][next.x] == 'H') { if (cost[next.y][next.x] > next.cost) { cost[next.y][next.x] = next.cost; if (map[next.y][next.x] == 'H') { ans = min(ans, cost[next.y][next.x]); continue; } q.push(next); } } } } printf("%d\n", ans > 999999999 ? -1 : ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Incorrect | 2 ms | 356 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Incorrect | 2 ms | 356 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |