백준 3197번 백조의 호수 ( C++ )

문제

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

 

해설

백조가 있는 곳에서 부터 얼음이 녹는것이 아닌 물이 있는곳 모든 곳에서 부터 얼음이 녹는것이 포인트

그렇기 때문에 얼음이 녹는것과 백조가 이동하는것을 따로 관리해야한다.

또한 백조가 있는곳은 물 위이기 때문에 백조가 있는곳도 물으로 처리해야 한다.

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int r, c, ret, startX, startY, x, y;
string line;
char mp[1504][1504];
int visited[1504][1504];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
queue<pair<int, int>> swan, swanTemp, melt, meltTemp;
 
void Qclear(queue<pair<int, int>> &q)
{
  queue<pair<int, int>> empty;
  swap(q, empty);
}
 
bool move_swan()
{
  while (swan.size())
  {
    tie(y, x) = swan.front();
    swan.pop();
    for (int i = 0; i < 4; i++)
    {
      int ny = y + dy[i];
      int nx = x + dx[i];
      if (ny < 0 || ny >= r || nx < 0 || nx >= c || visited[ny][nx] == 1)
        continue;
      visited[ny][nx] = 1;
      if (mp[ny][nx] == '.')
        swan.push({ny, nx});
      else if (mp[ny][nx] == 'L')
        return false;
      else
        swanTemp.push({ny, nx});
    }
  }
  return true;
}
 
void melting()
{
  while (melt.size())
  {
    tie(y, x) = melt.front();
    melt.pop();
    for (int i = 0; i < 4; i++)
    {
      int ny = y + dy[i];
      int nx = x + dx[i];
      if (ny < 0 || ny >= r || nx < 0 || nx >= c || visited[ny][nx] == 1)
        continue;
      if (mp[ny][nx] == 'X')
      {
        mp[ny][nx] = '.';
        meltTemp.push({ny, nx});
      }
    }
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> r >> c;
  for (int i = 0; i < r; i++)
  {
    cin >> line;
    for (int j = 0; j < c; j++)
    {
      mp[i][j] = line[j];
      if (mp[i][j] == 'L')
      {
        startY = i;
        startX = j;
        melt.push({i, j});
      }
      else if (mp[i][j] == '.')
      {
        melt.push({i, j});
      }
    }
  }
  swan.push({startY, startX});
  visited[startY][startX] = 1;
 
  while (move_swan())
  {
    melting();
    swan = swanTemp;
    melt = meltTemp;
    Qclear(swanTemp);
    Qclear(meltTemp);
    ret++;
  }
 
  cout << ret;
}