ColorfulTiles
SRM 472 · 2009-11-12 · by rng_58
SRM 472 · 2009-11-12 · by rng_58 · Dynamic Programming, Math
Problem Statement
Problem Statement
Taro likes colorful things, especially colorful tiles.
Taro's room is an H x W rectangle divided into 1 x 1 tiles. Each tile is one of the following four colors: red, green, blue or yellow. You are given aString[] room. If the j-th character of the i-th element is 'R', 'G', 'B' or 'Y', the color of the tile in the j-th column of the i-th row is red, green, blue or yellow, respectively.
He decided to change the color of some tiles so that no two adjacent tiles have the same color. Two tiles are adjacent if they share a side or a corner (so a tile has at most 8 adjacent tiles). He is allowed to change at most K tiles.
Return the number of ways to change tiles that satisfies the above conditions, modulo 1,000,000,007. Two ways are considered to be different if there is at least one tile of distinct color.
Taro's room is an H x W rectangle divided into 1 x 1 tiles. Each tile is one of the following four colors: red, green, blue or yellow. You are given a
He decided to change the color of some tiles so that no two adjacent tiles have the same color. Two tiles are adjacent if they share a side or a corner (so a tile has at most 8 adjacent tiles). He is allowed to change at most K tiles.
Return the number of ways to change tiles that satisfies the above conditions, modulo 1,000,000,007. Two ways are considered to be different if there is at least one tile of distinct color.
Constraints
- room will contain between 1 and 50 elements, inclusive.
- Each element of room will contain the same number of characters.
- Each element of room will contain between 1 and 50 characters, inclusive.
- Each character in room will be 'R', 'G', 'B' or 'Y'.
- K will be between 0 and the number of characters in room, inclusive.
Examples
0)
{"RG"}
1
Returns: 5
If he doesn't change any tiles, he can make "RG". If he changes the first tile, he can make "BG" or "YG". If he changes the second tile, he can make "RB" or "RY".
1)
{"BY"}
2
Returns: 12
All pairs of different colors are possible.
2)
{"RG",
"GR"}
2
Returns: 8
The eight ways are: RG RG BY YB BG YG RB RY BY YB GR GR YR BR GY GB
3)
{"BRYBGYRB"
,"GRYGYBBG"
,"RGBGYBYG"
,"YRBRGBYG"
,"RBGRBRGG"
,"RBGYRYBY"}
34
Returns: 489
4)
{"BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBBBBBBYYYYYBBBBBBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBBBYYYYYYYYYYYBBBBBBBB"
,"BBBBBBYYYYYYYYYYYYYYYYBBBBBBBBYYYYBBBBBYYYYBBBBBBB"
,"BBBBBBYYYYYYYYYYYYYYYYBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBBYYYYBBBBBYYYYBBBBBBB"
,"BBBBBBYYYBBBBBBBBBBBBBBBBBBBBBBBYYYYYYYYYBBBBBBBBB"
,"BBBBBBYYYYYYYYYYYYBBBBBBBBBBBBBBYYYYYYYYYBBBBBBBBB"
,"BBBBBBYYYYYYYYYYYYYYBBBBBBBBBBYYYYBBBBBYYYYBBBBBBB"
,"BBBBBBBBBBBBBBBBYYYYYBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBBBBBBBBBBBBBYYYBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBBBBBBBBBBBBBYYYBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBYYYBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBYYYBBBBBBBBBYYYBBBBBBBBYYYBBBBBBBBBYYYBBBBBB"
,"BBBBBBBYYYYBBBBBYYYYBBBBBBBBBBYYYYBBBBBYYYYBBBBBBB"
,"BBBBBBBBYYYYYYYYYYYBBBBBBBBBBBBYYYYYYYYYYYBBBBBBBB"
,"BBBBBBBBBBBYYYYYBBBBBBBBBBBBBBBBBBYYYYYBBBBBBBBBBB"
,"BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"}
825
Returns: 404506540
Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ColorfulTiles with a public method int theCount(vector<string> room, int K) · 93 test cases · 2 s / 256 MB per case