7132 : 폭탄 시뮬레이션
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N × M 격자 위에 여러 개의 폭탄(B)이 설치되어 있습니다.
폭탄 하나가 터지면 상, 하, 좌, 우 십자 방향으로 R칸만큼의 범위에 있는 모든 칸이 연쇄 파괴되며, 파괴 범위 내에 다른 폭탄이 존재하면 그 폭탄도 추가 연쇄 반응으로 터지게 됩니다.
벽(
격자 내의 모든 폭탄이 한꺼번에 터진다고 할 때, 최종적으로 파괴된 전체 칸(폭탄이 놓였던 칸 포함)의 개수를 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
폭탄 하나가 터지면 상, 하, 좌, 우 십자 방향으로 R칸만큼의 범위에 있는 모든 칸이 연쇄 파괴되며, 파괴 범위 내에 다른 폭탄이 존재하면 그 폭탄도 추가 연쇄 반응으로 터지게 됩니다.
벽(
#)이 있는 경우 폭발은 해당 방향의 벽 너머로 진행하지 못하고 벽에서 멈춥니다.격자 내의 모든 폭탄이 한꺼번에 터진다고 할 때, 최종적으로 파괴된 전체 칸(폭탄이 놓였던 칸 포함)의 개수를 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 세로 크기 N과 가로 크기 M이 공백으로 구분되어 주어집니다. (1 ≤ N, M ≤ 100)
둘째 줄부터 N개의 줄에 걸쳐 격자 정보(0:빈칸, #:벽, B:폭탄)가 주어집니다.
마지막 줄에 폭탄의 파괴 범위 반경 R이 정수로 주어집니다. (1 ≤ R ≤ 10)
둘째 줄부터 N개의 줄에 걸쳐 격자 정보(0:빈칸, #:벽, B:폭탄)가 주어집니다.
마지막 줄에 폭탄의 파괴 범위 반경 R이 정수로 주어집니다. (1 ≤ R ≤ 10)
출력 설명
폭발 종료 후 파괴된 전체 칸의 개수를 정수로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
0 B 0
0 0 0
0 0 0
2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5도움
초기에 모든 폭탄의 위치를 큐에 넣고 BFS 형태로 연쇄 반응을 돌리십시오. 각 방향으로 1부터 R까지 한 칸씩 확장하며 벽(
#)을 만나면 즉시 중단(break)해야 합니다.