복제

웹에서 "DIY" 공학 영상을 너무 많이 본 불행한 결과로, 농부 존은 실수로 자기 농장에 자가 복제 로봇을 풀어놓고 말았다!

농장은 \(N\times N\) 격자(\(3\le N\le 1000\))로 나타낼 수 있으며, 각 격자 칸은 비어 있거나 바위로 채워져 있고, 모든 테두리 칸은 바위로 채워져 있다. 바위가 아닌 일부 칸은 로봇의 가능한 시작 위치로 지정되어 있다.

농부 존은 처음에 가능한 시작 위치 중 하나에 로봇을 놓는다. 이후 매시간, 모든 로봇 복제본은 하나의 무리로 함께 북, 남, 동, 서 중 같은 방향으로 이동한다. 매 \(D\)시간(\(1 \leq D \leq 10^9\))이 지날 때마다 모든 로봇 복제본이 복제된다. 칸 \((x,y)\)에 있는 로봇이 복제되면 칸 \((x+1,y)\), \((x-1,y)\), \((x,y+1)\), \((x,y-1)\)에 새 복제본이 생기고, 원래 로봇은 \((x,y)\)에 남는다. 시간이 지나면 여러 로봇이 같은 칸을 차지할 수도 있다.

이동이나 복제로 인해 어떤 로봇이라도 바위 위로 이동하게 된다면, 모든 로봇이 즉시 정지한다. 농장의 테두리가 바위이므로 로봇들이 결국에는 반드시 정지하게 됨에 유의한다.

언젠가 로봇이 있을 수 있는 빈 칸의 개수를 알아내도록 소들을 도와주자.

문제 제공: Benjamin Qi

배점

• 테스트 케이스 4-5는 \(D=10^9\)를 만족한다.
• 테스트 케이스 6-8은 \(D=1\)을 만족한다.
• 테스트 케이스 9-12는 \(N\le 100\)을 만족한다.
• 테스트 케이스 13-20에는 추가 제약이 없다.

문제 제공: Benjamin Qi

첫째 줄에 공백으로 구분된 두 정수 \(N\)과 \(D\)가 주어진다. 다음 \(N\)개의 줄 각각에는 \(N\)개의 문자가 주어진다. 각 문자는 '.', 'S', '#' 중 하나이다. '.'과 'S'는 모두 빈 칸을 나타내며, 'S'는 로봇의 가능한 시작 위치를 나타낸다. '#'은 바위를 나타낸다.

첫 행과 마지막 행, 첫 열과 마지막 열의 모든 문자는 '#'이다.

언젠가 로봇이 있을 수 있는 칸의 개수를 정수로 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > December > Gold