RiseOJ – 글자로 색칠하기

설명

베시는 최근 페인트 세트를 선물 받았다. 캔버스는 $N \times M$ 직사각형의 칸들로 나타낼 수 있으며, 행은 위에서 아래로 $1\ldots N$ , 열은 왼쪽에서 오른쪽으로 $1\ldots M$ 으로 라벨이 붙어 있다( $1\le N,M\le 1000$ ). 칠해진 칸의 색은 'A'부터 'Z'까지의 대문자로 나타낼 수 있다. 처음에는 모든 칸이 칠해져 있지 않으며, 한 칸을 두 번 이상 칠할 수는 없다.

베시는 각 칸에 원하는 색을 정해 두었다. 어떤 칸들의 집합이 연결 요소를 이룬다면, 즉 집합의 임의의 칸에서 인접한 칸들을 따라 집합의 다른 임의의 칸에 도달할 수 있다면, 베시는 한 번의 붓질로 그 집합을 한 가지 색으로 칠할 수 있다. 두 칸이 변을 공유하면 인접한 것으로 간주한다.

예를 들어 $3\times 3$ 캔버스

AAB
BBA
BBB

는 다음과 같이 네 번의 붓질로 칠할 수 있다.

...    ..B    AAB    AAB    AAB
... -> ... -> ... -> BB. -> BBA
...    ...    ...    BBB    BBB

네 번보다 적은 붓질로 이 최종 결과를 만드는 것은 불가능하다.

전위 예술가인 베시는 결국 캔버스의 부분 직사각형만 칠하게 될 것이다. 현재 베시는 $$Q$$ 개( $1\le Q\le 1000$ )의 후보를 고려하고 있으며, 각 후보는 네 정수 $$x_1$$ , $$y_1$$ , $$x_2$$ , $$y_2$$ 로 나타낼 수 있다. 이는 행이 $$x_1$$ 부터 $$x_2$$ 까지, 열이 $$y_1$$ 부터 $$y_2$$ 까지인 모든 칸으로 이루어진 부분 직사각형을 뜻한다.

각 후보 부분 직사각형에 대해, 부분 직사각형 밖의 모든 칸은 칠하지 않은 채로 두면서 부분 직사각형 안의 각 칸을 원하는 색으로 칠하는 데 필요한 최소 붓질 횟수는 얼마인가? 이 과정에서 베시가 실제로 칠을 하는 것은 아니므로, 각 후보에 대한 답은 서로 독립적임에 유의한다.

참고: 이 문제의 시간 제한은 기본값보다 50% 크고, 메모리 제한은 기본값의 두 배인 512MB이다.

문제 제공: Andi Qu

제약

배점

테스트 케이스 1-2는 $N,M\le 50$ 을 만족한다.
테스트 케이스 3-5에서는 캔버스에 한 가지 색으로 이루어진 사이클이 없다. 즉, 다음 조건을 모두 만족하는 서로 다른 칸들의 수열 $c_1,c_2,c_3,\ldots,c_k$ 가 존재하지 않는다:

$$k>2$$
- $c_1,\ldots,c_k$ 모두 원하는 색이 같다.
- 각 $$1\le i에 대해 \(c_i$는 $c_{i+1}$과 인접하다. - $c_k$는 $c_1$과 인접하다.$

위의 $3\times 3$ 캔버스에는 한 가지 색으로 이루어진 사이클(왼쪽 아래 모서리의 네 개의 B)이 있음에 유의한다. 테스트 케이스 6-8에서는 원하는 색이 같은 칸들로 이루어진 모든 연결 요소가 변이 좌표축에 평행한 2×2 정사각형 안에 들어갈 수 있다. 위의 $3\times 3$ 캔버스는 이 성질을 만족하지 않는다(B 다섯 개로 이루어진 연결 요소는 2×2 정사각형 안에 들어갈 수 없다). 테스트 케이스 9-11에서는 원하는 색이 같은 칸들로 이루어진 모든 연결 요소가 변이 좌표축에 평행한 3×3 정사각형 안에 들어갈 수 있다. 위의 $3\times 3$ 캔버스는 이 성질을 만족한다. 테스트 케이스 12-20에는 추가 제약이 없다.

문제 제공: Andi Qu

입력 형식

첫째 줄에 $$N$$ , $$M$$ , $$Q$$ 가 주어진다.

다음 $$N$$ 개의 줄 각각에는 캔버스의 각 행에 원하는 색을 나타내는 $$M$$ 개의 대문자로 이루어진 문자열이 주어진다.

다음 $$Q$$ 개의 줄 각각에는 후보 부분 직사각형을 나타내는, 공백으로 구분된 네 정수 $$x_1,y_1,x_2,y_2$$ ( $1\le x_1\le x_2\le N$ , $1\le y_1\le y_2\le M$ )가 주어진다.

출력 형식

$$Q$$ 개의 후보 각각에 대해 답을 한 줄에 하나씩 출력한다.

예제 1

입력

4 8 9
ABBAAAAA
ABAAAABA
CAADABBA
AAAAAAAA
1 1 4 8
3 5 3 8
1 3 2 4
1 4 2 5
1 1 3 3
4 4 4 4
2 6 4 8
3 5 4 6
1 6 3 8

출력

설명

The first candidate consists of the entire canvas, which can be painted in six
strokes.

The second candidate consists of the subrectangle with desired colors

ABBA

and can be colored in three strokes. Note that although the cells at $$(3,5)$$ and
$$(3,8)$$ can be colored with $$A$$ in a single stroke if you consider the entire
canvas, this is not the case when considering only the cells within the
subrectangle.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > January > Platinum

올림피아드 > USACO > 2020-2021 > January > Platinum

태그

JudgeUSACO

글자로 색칠하기

평가 및 의견

풀이 제출