[백준 3197] 백조의 호수

https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

#include <cstdio>
#include <queue>
#include <cstring>
int R, C;
char board[1500 + 2][1500 + 2];
int sx = -1, sy = -1;
int ex = -1, ey = -1;

struct _st
{
	int x, y;
};
std::queue<_st> Water;
std::queue<_st> Swan;
std::queue<_st> TMP;
int w_visited[1500 + 2][1500 + 2];
int s_visited[1500 + 2][1500 + 2];

// dir
int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


void input()
{
	scanf("%d %d", &R, &C);
	for (int r = 0; r < R; r++) {
		scanf("%s", &board[r]);
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 'L') {
				if (sx == -1 && sy == -1) {
					sx = r;
					sy = c;
					Swan.push({ r, c });
					s_visited[r][c] = 1;
				}
				else {
					ex = r;
					ey = c;
				}
				board[r][c] = '.';
				Water.push({ r, c });
				w_visited[r][c] = 1;
			}
			else if (board[r][c] == '.') {
				Water.push({ r, c });
				w_visited[r][c] = 1;
			}
		}
	}
}

void melt_ice()
{
	// init
	TMP = {};

	while (!Water.empty()) {
		_st data = Water.front();
		Water.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (board[nx][ny] == '.') continue;
			if (w_visited[nx][ny]) continue;
			TMP.push({ nx, ny });	// 최전방 물좌표 담음 
			w_visited[nx][ny] = 1;
			board[nx][ny] = '.';
		}
	}
	Water = TMP;
}


bool move_swan()
{
	// init
	TMP = {};

	while (!Swan.empty()) {
		_st data = Swan.front();
		Swan.pop();

		if (data.x == ex && data.y == ey) return true;

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (s_visited[nx][ny]) continue;
			if (board[nx][ny] == 'X') TMP.push({ nx, ny });	// 다음번에 전진할 곳
			else Swan.push({ nx ,ny });	
			s_visited[nx][ny] = 1;
		}
	}
	Swan = TMP;
	return false;
}


int simulation()
{
	int day = 1;
	while (1) {
		// 빙판녹음 
		melt_ice();
		// 백조 움직임
		if (move_swan()) break;
		day++;
	}
	return day;
}


int main()
{
	input();
	int ans = simulation();
	printf("%d\n", ans);
	return 0;
}