TwoConvexShapes

SRM 553 · 2012-06-05 · by vexorian

SRM 553 · 2012-06-05 · by vexorian · Dynamic Programming

Show categories

Class Name: TwoConvexShapes

Return Type: int

Method Name: countWays

Arg Types: (vector<string>)

Problem Statement

A platypus has been given the mission to paint the cells on a grid either black or white according to the following two conditions:

For each color, all cells of that color must be connected. Formally, a pair of cells of color X is connected if there is a path of adjacent cells of color X between them. (Two cells are adjacent if they share a common edge.) We require that for each color, each pair of cells of that color must be connected.
All the cells of each color must form a convex shape. A group of cells of a given color is convex if in each row and each column the cells of that color form a connected segment (possibly taking the whole row or column). In other words, whenever two cells of the same color share the same row or the same column, all cells between them must also have that particular color.

The platypus is also allowed to paint the grid completely white or black.

The platypus may have already painted some of the cells. The current state of the grid is given as a String[] grid. The i-th character of the j-th element of grid that represents the cell at row j, column i is 'W' if it has been painted white, 'B' if it has been painted black, and '?' if it does not have a color yet. Let X be the number of different ways how to color the rest of the grid according to the above conditions. Return the value X modulo 1000000007 (10^9 + 7). Two ways to color a grid are different if the color of at least one cell differs.

Constraints

grid will contain between 1 and 50 elements, inclusive.
Element 0 of grid will contain between 1 and 50 characters, inclusive.
The remaining elements of grid will contain the same number of characters as element 0.
Each character in each element of grid will be one of 'B', 'W', and '?' (quotes for clarity).

Examples

{"??",
 "??"}
Returns: 14

Of all the 16 different ways to color the grid, only the following 2 are not valid. BW WB WB BW This is because cells of the same color are not connected.

{"B?",
 "??"}
Returns: 7

The following seven ways to color the grid are correct: BB BW BB BW BB BB BW BB BW WW WW WB BW BB

{"B?",
 "?B"}
Returns: 3

{"BW",
 "??"}
Returns: 3

{"WWB",
 "WWW",
 "WWW",
 "WWW"}
Returns: 1

All colors have already been picked. The only possible coloring is already valid.

{"BBBBBB",
 "WWBBBB",
 "WBBBBB"}
Returns: 0

This coloring of the grid is not valid, the black cells do not form a convex shape.

{"?????",
 "?????",
 "?????",
 "?????",
 "?????"}
Returns: 986

Bruteforce gives 986.

12)

{"?WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "B?WWWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "BB?WWWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "BBB?WWWWWWWWWWWWWWWWWWWWWWWWWWW",
 "BBBB?WWWWWWWWWWWWWWWWWWWWWWWWWW",
 "BBBBB?WWWWWWWWWWWWWWWWWWWWWWWWW",
 "BBBBBB?WWWWWWWWWWWWWWWWWWWWWWWW",
 "BBBBBBB?WWWWWWWWWWWWWWWWWWWWWWW",
 "BBBBBBBB?WWWWWWWWWWWWWWWWWWWWWW",
 "BBBBBBBBB?WWWWWWWWWWWWWWWWWWWWW",
 "BBBBBBBBBB?WWWWWWWWWWWWWWWWWWWW",
 "BBBBBBBBBBB?WWWWWWWWWWWWWWWWWWW",
 "BBBBBBBBBBBB?WWWWWWWWWWWWWWWWWW",
 "BBBBBBBBBBBBB?WWWWWWWWWWWWWWWWW",
 "BBBBBBBBBBBBBB?WWWWWWWWWWWWWWWW",
 "BBBBBBBBBBBBBBB?WWWWWWWWWWWWWWW",
 "BBBBBBBBBBBBBBBB?WWWWWWWWWWWWWW",
 "BBBBBBBBBBBBBBBBB?WWWWWWWWWWWWW",
 "BBBBBBBBBBBBBBBBBB?WWWWWWWWWWWW",
 "BBBBBBBBBBBBBBBBBBB?WWWWWWWWWWW",
 "BBBBBBBBBBBBBBBBBBBB?WWWWWWWWWW",
 "BBBBBBBBBBBBBBBBBBBBB?WWWWWWWWW",
 "BBBBBBBBBBBBBBBBBBBBBB?WWWWWWWW",
 "BBBBBBBBBBBBBBBBBBBBBBB?WWWWWWW",
 "BBBBBBBBBBBBBBBBBBBBBBBB?WWWWWW",
 "BBBBBBBBBBBBBBBBBBBBBBBBB?WWWWW",
 "BBBBBBBBBBBBBBBBBBBBBBBBBB?WWWW",
 "BBBBBBBBBBBBBBBBBBBBBBBBBBB?WWW",
 "BBBBBBBBBBBBBBBBBBBBBBBBBBBB?WW",
 "BBBBBBBBBBBBBBBBBBBBBBBBBBBBB?W"}
Returns: 73741817

Each of the 2^30 ways to color the remaining cells in the grid is valid.

Submissions are judged against all 101 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TwoConvexShapes with a public method int countWays(vector<string> grid) · 101 test cases · 2 s / 256 MB per case