페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8255
서브태스크

베시는 별 사진을 찍고 싶어! 4초 1024MB

문제

베시는 멋진 망원경을 사용해 밤하늘의 모든 별을 사진으로 찍고 있다. 그녀의 망원경은 N×N 크기의 사진을 촬영할 수 있으며, 각 픽셀은 별이 있거나(empty sky) 없을(empty sky) 수 있다. 각 별은 정확히 하나의 픽셀로 표현되며, 두 개 이상의 별이 같은 픽셀을 공유하는 경우는 없다.

그런데 밤새 이상한 일이 벌어졌다. 모든 별이 사라지거나, 오른쪽으로 A 픽셀, 아래쪽으로 B 픽셀(0≤A,B≤N)만큼 이동했다. 별이 사라지거나 사진 경계를 넘어가면, 두 번째 사진에는 더 이상 나타나지 않는다.

베시는 별들의 이동 전과 후를 사진으로 찍었지만, 이미지 편집 프로그램인 Mootoshop에서 실험하다가 실수로 두 사진을 겹쳐버렸다.
이제 그녀는 사진을 다음과 같은 방식으로 볼 수 있다.

  • 흰색(W, White): 두 사진에서 모두 빈 공간(즉, 별이 없는 부분)

  • 회색(G, Gray): 별이 한 사진에서만 존재하는 경우

  • 검은색(B, Black): 별이 두 사진에서 모두 존재하는 경우

또한, 베시는 새로운 별이 두 번째 사진의 프레임 안으로 들어온 경우는 없다는 것을 기억하고 있다. 즉, 첫 번째 사진에는 모든 별이 포함되어 있었다.

주어진 최종 사진을 보고, 별이 이동하기 전 최소한 몇 개의 별이 존재했는지를 구하는 프로그램을 작성하라.
만약 어떤 별의 배치도 주어진 최종 사진을 만들 수 없다면 -1을 출력하라.


입력

첫 번째 줄에는 T(1≤T≤1000)가 주어지며, T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

  • 첫 번째 줄에 N, A, B가 주어진다. (1≤N≤1000)

  • 이후 N개의 줄에는 N×N 크기의 최종 사진이 주어진다.

    • 각 줄은 길이 N의 문자열이며, 각 문자는 W(흰색), G(회색), B(검은색) 중 하나이다.

단, 모든 테스트 케이스에 대해 N^2의 합은 10^7을 넘지 않음이 보장된다.


출력

각 테스트 케이스마다, 이동 전 최소한 몇 개의 별이 있었는지 출력하라.

만약 주어진 최종 사진을 만들 수 있는 초기 상태가 존재하지 않는다면 -1을 출력하라.


부분문제

번호 점수 조건
#110점

A=B=0

#220점

A=1,\ B=0,\ N\le10

#330점

A=1, B=0

#440점

추가 제약 조건 없음


예제1

입력
1
300
WWB
BBB
GGG
출력
7

이동이 없었으므로( A = 0, B = 0 ) 첫 번째 사진은 다음과 같아야 한다.

( .: 빈 공간, *: 별)

..*

***

***

두 번째 사진에서는 아래쪽 행의 별들이 사라졌다.

..*

***

...

이 방법이 최종 사진을 만드는 유일한 방법이므로, 초기 별의 최소 개수는 7개이다.


예제2

입력
3
512
GWGWW
WGWWW
WBWGW
WWWWW
WWGWW
311
WWW
WBW
WWW
310
GGB
GGW
WWW
출력
4
-1
4

  1. 첫 번째 테스트 케이스에서 최소 4개의 별이 존재해야 했다. 가능한 별의 초기 위치는 다음과 같다.

    • (1,1), (3,2), (2,2), (1,3)

    • 이 중 (2,2)의 별은 사라졌고, 나머지 별들은 이동했다.

  2. 두 번째 테스트 케이스에서는 어떤 배치도 주어진 최종 사진을 만들 수 없으므로 -1을 출력해야 한다.

  3. 세 번째 테스트 케이스에서는 최소 4개의 별이 존재해야 했다. 가능한 초기 위치는 (1,1), (1,2), (1,3), (2,1)이다.


출처

USACO 2025 January Bronze

역링크