8111: USACO 2021 January Contest, Platinum Problem 3. Paint by Letters
[Creator : ]
Description
Bessie has recently received a painting set. The canvas can be represented as an N×M rectangle of cells where the rows are labeled 1…N from top to bottom and the columns are labeled 1…M from left to right (1≤N,M≤1000). Once painted, the color of a cell can be represented by an uppercase letter from 'A' to 'Z.' Initially, all cells are uncolored, and a cell cannot be painted more than once. Bessie has specified the color that she desires for each cell. She can paint a set of cells with a single color in one stroke if the set forms a connected component, meaning that any cell in the set can reach any other via a sequence of adjacent cells. Two cells are considered to be adjacent if they share an edge.
For example, the 3×3 canvas
can be colored in four strokes as follows:
It is not possible to produce the end result using less than four strokes.
Being an avant-garde artist, Bessie will end up painting only a subrectangle of the canvas. Currently, she is considering Q candidates (1≤Q≤1000), each of which can be represented by four integers $x_1, y_1, x_2, y_2$. This means that the subrectangle consists of all cells with row in the range $x_1$ to $x_2$ inclusive and column in the range $y_1$ to $y_2$ inclusive.
For each candidate subrectangle, what is the minimum number of strokes needed to paint each cell in the subrectangle with its desired color while leaving all cells outside the subrectangle uncolored? Note that Bessie does not actually do any painting during this process, so the answers for each candidate are independent.
For example, the 3×3 canvas
AAB BBA BBB
can be colored in four strokes as follows:
... ..B AAB AAB AAB ... -> ... -> ... -> BB. -> BBA ... ... ... BBB BBB
It is not possible to produce the end result using less than four strokes.
Being an avant-garde artist, Bessie will end up painting only a subrectangle of the canvas. Currently, she is considering Q candidates (1≤Q≤1000), each of which can be represented by four integers $x_1, y_1, x_2, y_2$. This means that the subrectangle consists of all cells with row in the range $x_1$ to $x_2$ inclusive and column in the range $y_1$ to $y_2$ inclusive.
For each candidate subrectangle, what is the minimum number of strokes needed to paint each cell in the subrectangle with its desired color while leaving all cells outside the subrectangle uncolored? Note that Bessie does not actually do any painting during this process, so the answers for each candidate are independent.
Input
The first line contains N, M, and Q.
The next N lines each contain a string of M uppercase characters representing the desired colors for each row of the canvas.
The next Q lines each contain four space-separated integers $x_1,y_1,x_2,y_2$ representing a candidate subrectangle $(1≤x_1≤x_2≤N, 1≤y_1≤y_2≤M)$.
The next N lines each contain a string of M uppercase characters representing the desired colors for each row of the canvas.
The next Q lines each contain four space-separated integers $x_1,y_1,x_2,y_2$ representing a candidate subrectangle $(1≤x_1≤x_2≤N, 1≤y_1≤y_2≤M)$.
Output
For each of the Q candidates, output the answer on a new line.
Sample 1 Input
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
Sample 1 Output
6
3
2
1
4
1
3
2
2
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
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.
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.