#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;
}
Compilation message
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 time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
25720 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
25828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
25720 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
25828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
