RiseOJ – 별들의 중첩

설명

*참고: 이 문제의 시간 제한은 기본의 두 배인 4초이다.*

베시는 자신의 멋진 망원경으로 밤하늘의 모든 별을 사진에 담고 있다. 베시의 망원경은 각 픽셀이 별이거나 빈 하늘인 $N \times N$ ( $1 \leq N \leq 1000$ ) 크기의 별 사진을 찍을 수 있다. 각 별은 정확히 한 픽셀로 표현되며, 서로 다른 두 별이 같은 픽셀을 공유하는 일은 없다.

밤사이에 하늘의 별들에게 이상한 일이 일어난다. 모든 별은 사라지거나, 오른쪽으로 $$A$$ 픽셀, 아래로 $$B$$ 픽셀 이동한다 ( $0 \leq A,B \leq N$ ). 별이 사라지거나 사진 경계 밖으로 이동하면 두 번째 사진에는 더 이상 나타나지 않는다.

베시는 별들의 위치가 바뀌기 전과 후에 사진을 찍었지만, 무토샵(Mootoshop)에서 이것저것 실험하다가 실수로 한 사진을 다른 사진 위에 겹쳐 버렸다. 이제 베시가 볼 수 있는 것은, 두 사진 모두 비어 있던 곳의 흰색 픽셀, 정확히 한 사진에만 별이 있던 곳의 회색 픽셀, 두 사진 모두에 별이 있던 곳의 검은색 픽셀이다. 베시는 또한 두 번째 사진의 프레임 안으로 새로 들어온 별이 없다는 것, 즉 첫 번째 사진에 밤하늘의 모든 별이 담겨 있다는 것을 기억한다.

최종 사진이 주어졌을 때, $$T$$ ( $1 \leq T \leq 1000$ )개의 독립적인 테스트 케이스에 대해 이동 사건 이전 하늘에 있던 별의 최소 개수를 구하여라. 어떤 별들의 배치로도 주어진 최종 사진을 만들 수 없다면 $$-1$$ 을 출력한다.

문제 제공: Suhas Nagar

제약

배점

입력 3: $$A=B=0$$
입력 4-7: $A=1, B=0, N\le 10$
입력 8-9: $$A=1, B=0$$
입력 10-12: 추가 제약 없음.

문제 제공: Suhas Nagar

입력 형식

첫째 줄에 $$T$$ 가 주어지고, $$T$$ 개의 테스트 케이스가 이어진다.

각 테스트 케이스의 첫째 줄에 $$N$$ $$A$$ $$B$$ 가 주어진다.

이어서 겹쳐진 사진의 각 행을 나타내는 $$N$$ 개의 줄이 주어진다. 위에서 $$i$$ 번째 행은 문자열 $c_{i,1}c_{i,2}\dots c_{i,N}$ 으로 표현되며, 각 $c_{i,j} \in \{W,G,B\}$ 는 각각 흰색, 회색, 검은색을 나타낸다.

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

출력 형식

각 테스트 케이스에 대해, 이동 전에 존재했던 별의 최소 개수를 출력하고, 불가능하면 $$-1$$ 을 출력한다.

예제 1

입력

1
3 0 0
WWB
BBB
GGG

출력

설명

In this example, there is no shifting. The first photo is as follows: (. for
sky, * for star)

..*
***
***

The second photo, where the stars on the bottom row disappeared, is as follows:

..*
***
...

This is the only way to produce the superimposed photo, so the minimum possible
number of initial stars is $$7$$ .

예제 2

입력

3
5 1 2
GWGWW
WGWWW
WBWGW
WWWWW
WWGWW
3 1 1
WWW
WBW
WWW
3 1 0
GGB
GGW
WWW

출력

4
-1
4

설명

In the first case, there were at least $$4$$ stars at the start. If we let $$(r,c)$$
denote the intersection of the $$r$$ th row from the top and $$c$$ th column from the
left, one possibility is that they were initially at $$(1,1), (3,2), (2,2),$$ and
$$(1,3)$$ . All the stars shifted, except for the one at $$(2,2)$$ which disappeared.

In the second case, there is no arrangement of stars in the initial photo that
can produce the middle black pixel given the shift.

In the third case, there were at least $$4$$ stars at the start. One possibility
is that they were initially at $$(1,1), (1,2), (1,3),$$ and $$(2,1)$$ . In the second
photo, the star originally at $$(1,1)$$ disappeared and the star originally at
$$(1,3)$$ moved off frame. The other two stars shifted to the right by 1.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > January > Bronze

올림피아드 > USACO > 2024-2025 > January > Bronze

태그

JudgeUSACO

별들의 중첩

평가 및 의견

풀이 제출