Submission #72418

#	Time	Username	Problem	Language	Result	Execution time	Memory
72418		동진의 (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	0 / 100	24 ms	25828 KiB

aqua

#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 (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]

• Subtask 1: 0 / 36
• Subtask 2: 0 / 64