[백준 16918] 봄버맨

www.acmicpc.net/problem/16918

16918번: 봄버맨

뭔가 쉬운데 헷갈렸던 문제..

bfs가 살짝 필요한 구현문제이다.

 

3초짜리폭탄을 설치하고 1초를 냅둔다.

2초에 빈자리에 폭탄을 설치한다.

폭탄이 0초가 되면 터지고 주변에 폭탄이 있다면 같이 터진다.

그뒤로 폭탄 설치와 폭발이 반복이다 폭탄 설치는 짝수 초에 계속된다.

 

그래서 남은 폭탄 시간을 저장하는 이차원 배열 time을 만들었다.

폭탄 설치 시 3이 저장되며 폭탄이 없는 공간은 -1이다.

배열이 0이 되면 폭탄이 터져서 주변과 함께 -1이 된다.

이때 주의할 점은 폭탄이 터지는 시점에 주변에 0인 폭탄이 있다면 같이 터트리면 안된다. 왜냐하면 0초 남은 그 폭탄도 따로 터트려야 주변 폭탄을 모두 제거할 수 있기 때문

 

그래서 bfs시 time[nr][nc] == 0인 경우는 빼야 한다.

#include <stdio.h>

using namespace std;

int r, c, n;
int time[200][200];

void decreaseTime()
{
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      if (time[i][j] > 0)
        time[i][j]--;
    }
  }
}

void putBomb()
{
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      if (time[i][j] == -1)
      {
        time[i][j] = 3;
      }
    }
  }
}

int dr[4] = {0, 0, -1, 1};
int dc[4] = {1, -1, 0, 0};
void bomb()
{
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      if (time[i][j] == 0)
      {
        time[i][j] = -1;
        for (int k = 0; k < 4; k++)
        {
          int nr = i + dr[k];
          int nc = j + dc[k];

          if (nr < 0 || nc < 0 || nr > r - 1 || nc > c - 1 || time[nr][nc] == 0)
          {
            continue;
          }

          time[nr][nc] = -1;
        }
      }
    }
  }
}

int main(void)
{
  scanf("%d%d%d", &r, &c, &n);

  for (int i = 0; i < r; i++)
  {
    char tmp[201];
    scanf("%s", tmp);

    for (int j = 0; j < c; j++)
    {
      if (tmp[j] == 'O')
      {
        time[i][j] = 3;
      }
      else
      {
        time[i][j] = -1;
      }
    }
  }

  for (int s = 1; s <= n; s++)
  {
    decreaseTime();
    if (s % 2 == 0)
    {
      putBomb();
    }
    bomb();
  }

  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      if (time[i][j] == -1)
      {
        printf(".");
      }
      else
      {
        printf("O");
      }
    }
    printf("\n");
  }
  return 0;
}