Problem Statement
You just designed another single-player game.
This one is called the Flipping Game.
The game is played on a rectangular board that is divided into n rows by m columns.
The game is played using square tiles.
The tiles have the same size as the unit square cells on the board.
Each tile has one side white and the other side black.
You are given n, m, and a
More precisely, the character x[r][c] represents the cell in row r, column c of the board:
'w' means that this cell contains a tile that is white (i.e., white on top, black on bottom), 'b' is a black tile, and 'e' is an empty cell without a tile.
There will always be at least one white tile, at least one black tile, and at least one empty cell.
The game starts with a special turn in which you fill in all empty cells using some spare tiles.
You have an unlimited supply of spare tiles that all look the same as the tiles on the board.
All the new tiles must be placed with the same color facing up.
I.e., you may either change all empty cells into white cells, or change all empty cells into black cells.
Once you do that, you may take zero or more ordinary turns.
Each ordinary turn looks as follows:
Choose any tile T, note its color C, and flip the tile T to show the opposite color.
Then, the flip cascades: whenever you flip some tile X and there is a tile Y adjacent to X such that the color of Y is also C, you have to flip Y as well.
Two tiles are considered adjacent if they share a side.
The turn ends when the cascade ends and there are no more tiles you have to flip.
You win the game when the entire board has the same color.
Determine and return the smallest number of turns needed to win the game.
Note that the special turn counts as one of the turns.
Also note that it is always possible to win the game.
Definition
- Class:
- TheFlippingGame2
- Method:
- MinimumMoves
- Parameters:
- int, int, String[]
- Returns:
- int
- Method signature:
- int MinimumMoves(int n, int m, String[] x)
- (be sure your method is public)
Constraints
- n will be between 2 and 20, inclusive.
- m will be between 2 and 20, inclusive.
- x will contain exactly n elements.
- Each element of x will contain exactly m elements.
- Each element of each element of x will be one of 'b', 'w', and 'e'.
- If we concatenate all elements of x, it will contain at least one 'b', at least one 'w', and at least one 'e'.
Examples
3
3
{"bwe","web","ebw"}
Returns: 3
You need at least three turns to win the game. One possible way to win the game in three turns looks as follows. In the special turn, place white tiles onto all empty cells, obtaining a board that looks as follows: bww wwb wbw In the first ordinary turn, flip the white tile in the bottom right corner. As all the tiles adjacent to this tile are black, there will be no cascading. The resulting board will look as follows: bww wwb wbb Finally, in the second ordinary turn flip any of the remaining white tiles. This time the cascade of flips will cause all the remaining white tiles to flip to black as well, leaving us with a completely black board. It is also possible to win in three turns if black tiles are added in the special turn.
3
3
{"bwe","wbw","ewb"}
Returns: 3
Whether you choose to fill missing tiles with black-side up or white-side up, you need 3 turns to end the game.
4
4
{"beww","beww","beww","wewe"}
Returns: 2
This time it is strictly better to use white tiles in the special turn. You can then win the game simply by flipping any one of the sixteen tiles. (If you were to use black tiles in the special turn, you would need at least two more turns to win the game.)
20
20
{"bwbwbwbwbwbwbwbwbwbw","wbwbwbwbwbwbwbwbwbwb","bwbwbwbwbwbwbwbwbwbw","wbwbwbwbwbwbwbwbwbwb","bwbwbwbwbwbwbwbwbwbw","wbwbwbwbwbwbwbwbwbwb","bwbwbwbwewbwbwbwbwbw","wbwbwbwbebwbwbwbwbwb","bwbwbwbwewbwbwbwbwbw","wbwbwbwbebwbwbwbwbwb","bwbwbwbwewbwbwbwbwbw","wbwbwbwbebwbwbwbwbwb","bwbwbwbwewbwbwbwbwbw","wbwbwbwbebwbwbwbwbwb","bwbwbwbwewbwbwbwbwbw","wbwbwbwbwbwbwbwbwbwb","bwbwbwbwbwbwbwbwbwbw","wbwbwbwbwbwbwbwbwbwb","bwbwbwbwbwbwbwbwbwbw","wbwbwbwbwbwbwbwbwbwe"}
Returns: 16
If you fill in missing tiles with black side up, you need 18 turns. Otherwise, you need 17 turns.
2
8
{"ewewbbbb","bwebewww"}
Returns: 3
12
6
{"bewbbe","eebwbw","eeebwe","bbeeww","eebbee","bbwbww","wwbwww","eeewwe","ebwebe","eewewe","eweeeb","eeebwe"}
Returns: 3
9
6
{"ewbbww","bbbbee","weeeee","bbeebe","eewbwe","weebee","ewbeww","wwwwbe","bbewee"}
Returns: 3
2
6
{"wbebbb","ebbebe"}
Returns: 2
12
11
{"eebbeebbwwb","ewwwebbbwww","bbbewebwbbb","ebewweebeee","ewbwbbewbbw","wbeeebwbeee","weewewewbbw","ebwbbbeeeew","webwebeewwb","bbwweebbebe","eebbbwebwbw","beebbebwbbb"}
Returns: 3
2
15
{"ebbeeeeweeebbeb","eewwbbbbbebbbwb"}
Returns: 2
16
16
{"wwbeeewewwebwwwe","bwbebebbwweweebe","wwwbeebeebewbeew","beeeeebwweweewbe","wwwbebeweewbeeee","webebbebeebewbbb","bwewbwewbwbewebe","ebbbbewbwewebbwb","bweebwwebbewebwb","ebewewebbwwbeebb","wbebeewwebwbebwe","eeewbewbweebebwb","bwweebebbwbeebew","bebbewbebbwwweew","ebewbbwbwbeewbwb","ewebbbwebewwbbbb"}
Returns: 3
14
17
{"ebbebebewebbwwbwe","wbeewbwwebewbebeb","weweeewwwwewbwweb","wbewbbbwbeeeewewe","bbewwebwbeebbbbew","webeeeeweeeebeewb","eebwbwbbbewbbeebe","webeeebeebewbbwee","wbebwbeewwbwebbbb","eebwwewwwwbwweewb","ebweeebeewewbbbwb","wwebweeweebwbbebw","eeebwbwewweewbebb","wewweewwbbweebewe"}
Returns: 3
20
4
{"eeeb","weew","ewww","weee","beww","bbee","bwwe","ewww","bebe","bwew","bweb","eeew","eebe","beww","bebe","beew","eeww","wbbw","weee","ebwe"}
Returns: 2
17
19
{"ebwbbbeewbbbeeebbwe","beeewbbbbebbwbwbwwb","bbewwewbbewweeeeebe","bbwbewbeeeebweewbbw","wbbeweewwbeebwbwbeb","ebebwewewbbeweebebw","webewbeewbbwbwebbwe","bbbbebweweebeeewbbe","weweeeewbweebebwewb","wbeeebwebbbeeewbeee","bwebbeewebeeweeewee","eebebeeweebebbbwbwe","wbeeebweweebewbeeeb","wbeebebebebbebbewee","bbbwbbwebewbebebbeb","wbbwebeewebbbbebbbw","bbwbwebebwbbeebeewe"}
Returns: 3
11
20
{"ebewewebebweweeweebb","bwwbebeeeeebebeeeewe","weewewebewbebeweebee","wweeeeewwewbbeebbwwb","bewbebbbwbwewwwweeew","wwebwewweebbeeewbeeb","ebeebbbweeeeewbewbee","wbeweebbbbweeeeebwwe","eeeeewebewwbbwbbewbe","eeeebwwwbewweeeebebw","wwbewewwwebebewbewew"}
Returns: 3
2
15
{"wwbbeebweewweew","wbweewweewbbeee"}
Returns: 3
5
18
{"eebwbbwwwbweeebwbw","bewwbwbwebweeeeeee","bbweebbwwweewebwww","wbbwewwbbbbbwwwwee","beebewbebwwewwweee"}
Returns: 4
15
15
{"eewbwwebweeebwe","wwewwbbwewwweee","eeewbwbbbwewwew","beeeeweeeewwewe","beewewbwwewwwwe","wwwwwweewweweew","bewbeebwwweebbw","wwwbeeebwwbeebw","eeewewweeeebweb","ewebbeeewbebewe","wwewbewwbwwbbew","webwbbeeebewwbe","ebebbwweebweebw","ewbewweewwewbew","ewwwwbeebebewww"}
Returns: 3
17
7
{"ewewbbw","wwwwwbe","eweewew","wwwbwwb","bwbeebe","weewwew","bwwbbwe","eeeweee","ewwbeee","webeweb","bebweww","eewweee","ewwbwee","wwbbbww","eewwwwe","eeweeew","bwwbbbe"}
Returns: 2
9
16
{"ewwwbeeewwwebbeb","weeeebeeweweeebw","eweewewbebebebew","weeeebwbeeewbweb","eewwbbebwbewwwwe","ebweewwebbwbbeew","bwewwewwbbbebewe","wewwewbewbwbbebw","eewwewbwwwbebwww"}
Returns: 3
20
3
{"eeb","wbe","ebw","eeb","eew","ewe","wee","beb","wbw","wwe","wee","wew","wwb","bbb","ebe","wbe","bbe","ebw","ewe","bew"}
Returns: 5
4
20
{"wwwbwbbbweeebbwweeww","weeweweewwewbbewwwbe","ebeebebeeebewewewbew","wwweeeebewebbwwwewbw"}
Returns: 2
6
5
{"ewwwb","wbwwb","eewwb","eeeww","bebww","wewew"}
Returns: 2
11
17
{"wweebeeeeebwewwee","wwbbwbbebbeweewee","weewwbbwwwweeewee","wewweeebewewbbbeb","beebeewweeeeeebeb","wbewewwbbbebeweww","eebwweewwebeewwee","ebwbweewweebeweww","bwebwweewwewwebbb","ewbwwwwbwbebewebe","bwwwbwwebwbwbebwb"}
Returns: 3
20
5
{"eeeew","eebeb","eweew","bewbe","weebb","ewwee","eeeew","bewee","bbebb","weweb","bwwwe","wbwew","wewbe","bbewe","wbweb","bweeb","wwbbe","bebbb","ewebe","eewwe"}
Returns: 3
8
9
{"ebeeewbew","eweebbewb","webbbbbbe","beeeebbbw","beebeebeb","bebwwewwe","ebwewewbe","wbebbeebb"}
Returns: 2
18
8
{"weewbeee","bweewbwb","eebbewwe","bbeeewbb","wbewbweb","ewewewee","beeewebb","bbbewbww","bwwwbebe","eweewbbb","eebwbbbe","eewwweew","bwbbeeeb","eeebebbe","bwebewew","wbeweeww","wwebwewb","ewebbeee"}
Returns: 3
9
4
{"wwbb","bwbb","bbbw","ewbe","ebwe","weew","ewew","ebee","bwwe"}
Returns: 2
12
6
{"beeebw","eewbww","bebwee","bebbbe","bewbbw","wbwbww","eewebb","bebwbe","ebebwb","bbeeeb","ebwbbe","eeebeb"}
Returns: 2
18
7
{"ewbewbw","wewwwbe","bwebeeb","wbbebbe","bwebebe","eweeeew","bbewbbb","wbbbwbw","bwweewb","beewbeb","bbeebww","webbwbb","bebbwwb","ebbebew","bebbeeb","eeebwbw","webbwww","bbeewwb"}
Returns: 4
15
14
{"ebbewwebbbbbwe","bewewwebwebwwb","eebbbwbebwbweb","wbeebwwebbwbbb","wwwbwbewebeeew","bebebbewwwwbee","eebbbewbbeebbb","ewwbbbeebbebee","bbbbbebewbbebb","beebwbebbeeebb","weeebwebbbbebe","eebebebbbewbwe","wbeebwebeeweew","wwbwbbbbwwwwbb","bwebweeewbbebb"}
Returns: 3
16
9
{"bwbewwbeb","ebebwbbbe","bwbwbbebb","wbbeebwbw","bwbbweeee","bbwwwbeew","bewbeebbw","bewewbwbb","bbbeeebeb","wwbwwbbeb","beewbwwbb","bwbbebeeb","bwbeeeeee","ebebbwebe","ebwewebbb","bwebebbwb"}
Returns: 2
9
18
{"bbewewbbebebwebwbe","bwewbbbewewwwbebwb","webwwebebebbbewbww","ebweebbbwbebbbebbw","wbebwbbbbewbbbebbe","wbwwbbebbbewwbeebb","eeeebbwweeebeeeweb","bbwebbwbewbeeeeebb","bbwewbwbwbewbwbbee"}
Returns: 3
14
16
{"wwbweeweewbweewe","eeeweeewbbeebebe","ewbbbwbbbbbeewee","beeebwbwweeewwee","bwbbeeebbbeeebee","bbwwbbebebeeeeew","weebwebeebwbebew","bbebbbbbebeeewbe","bwbbwbbwebbeeebe","bweewbeebbwbebwb","bwwwbeeweeweeewb","webbbweeebewbbbb","wbbbwbbeeeeeeebb","webeweebbebewwbe"}
Returns: 2
12
16
{"ebeeeewbebebwewb","ewbwbbwebbeebbwe","bbewebebbbeewebe","beebwweeebwbbebb","ebwwbewewbwebbee","wbbbbeweeweebeww","bbbwbbewwbebeeeb","bwbeebebbebbbebb","ebbwebbeeeewwbwe","ebbeebwbeeebbebb","bebbbwbeeweewbeb","ewbweewbwwebeeww"}
Returns: 2
20
10
{"ebewbwweeb","wwebwwbbwb","bbweeebeew","wwbwbwbbwe","eewbbewbwe","wwbebwebbb","webwwwwweb","wbebweeweb","bbwwbbbeww","ebwwbebeww","wbewwwewwb","bbewbbbwwb","ebeebbebww","wbebbbwwbe","ebwewwwweb","wwwbewbwbb","eewwwbewbw","ebewbwewew","webbwwwebb","bbbbewbbbe"}
Returns: 3
8
13
{"wbewwewewbwwb","ewewbewwbbbew","wwewbbbwwwbbb","bewbwwwbbwwwb","bebwweeewbewb","eeewweebwewwb","ebbeewbbwbbeb","ebwbwwwbwewww"}
Returns: 4
2
13
{"bwwebwwwebbww","bbwbbwebewweb"}
Returns: 3
5
4
{"wbwb","bewb","wbwb","bwww","bbbe"}
Returns: 3
20
18
{"bwebbwwbbwweebwwwb","ebwbbeeeewwwwwbeeb","bebweweebwbwwwwwew","bwbwbwwbbwbbwweweb","wbbwbwbwwewwbbebwe","bewbebwbwbbbbbwwww","ebwwbbbbewbwbbbbbb","beewweebbbbweewwee","bwebebeewebwwwwwew","ebbbbwbebbbwbbwbww","bbbwewbbwwwewbebbe","bwbbwwwebeewbbbwew","eebwwwewwbbbbwbbbe","ewebwbbbwbwwbebbbe","wwewbwbewwwwbeeewe","bebwebwbbbbewbweew","ewbwbbwbwbbwwbbwwb","weewwbwbeebewewbeb","eebbwebbbwwbwebbwb","bbwwbbweewbeebbbww"}
Returns: 4
20
16
{"ebbwbbwbbbeewwww","wbbbwwwwbwbwbebw","bwewbwbbebbebbwb","wewwbwwbewebbbew","bbwbwebwbebwweeb","ewwwbwwbbwweewbb","wwbbweewwbwebebw","ebeebwewweebwbww","ebebebebbwbwbebw","bbebwwwbbbwbbbew","bbbeewbebebwebbb","bwwwbbbwbbbebbbb","bbwbwebbwbwewbwe","eewwwwbwbbwbbbew","wwebbebwewwbbweb","webbewbeebbbweee","wbeewbwbbbbbeewe","bbwbwwwbwbwweebw","ewbbbweweewbeweb","bbebbbbbbewwwebw"}
Returns: 4
17
4
{"wwbb","bbbe","ebwb","wwbb","bbeb","bwbb","eeew","bbbw","wwwb","wbwe","wbew","bebb","bwbe","eweb","bwbw","bbee","bebb"}
Returns: 3
5
12
{"wbbbebbwewww","bbeebbwweewb","wwbeweweebwe","ewebbwebebww","ebbbwwbebwew"}
Returns: 3
16
20
{"bbwewewbwwwbeewwwwbb","beebbwbewbbbbeewwbwb","webebbbwwwbwbewewwww","bbewbbwebewbewewwbeb","ewwbeewebwbebwwbbbbw","wwbwbbwwbwwewbwbbbww","bewbwwbbbwewbbwbeeew","eewbwwebweeebewwebew","wwwbwewebwbbewewbwwe","eewbbbewwbbebbewebww","bwebbeebbbwbbwwbbbeb","wbbwbweewbebwwbebweb","wbwbwwbbewbebbebbwwb","ebbebbwwwbbbbbwewbwe","bwwbwebwbwwwwebwbeee","eeebwbebwwebbwbwbwbw"}
Returns: 5
7
14
{"wwwewwbbwwbbew","bebwewwbebwbbb","wbebbwbweebeeb","wwwbwwbbwwwwbe","wbwwwwewewwbww","wewbbbwwewbeeb","wwbwbwbbbwbbbe"}
Returns: 4
4
6
{"wbbewb","weeeww","beweww","eewbee"}
Returns: 2
10
15
{"wwebbebwwebeewe","wbebwbeebbwewbb","ebbewwwwebeewew","ewbbbbbbewewwwb","ewwbbeewwweeebe","webebwbwweewwwe","wwbewbwbbeewebe","beweewwwwwwweee","bbwbbbewebbwwwe","eebbbwwebebeebw"}
Returns: 3
8
11
{"wwwwewewwwb","wweeeewwwbw","ebebbwbewwe","bewbwwebeew","ewweewweebb","eewwwwwbweb","wwbeeewwwwb","ewewebbweww"}
Returns: 2
2
8
{"wbbeeewb","ewbeweee"}
Returns: 3
20
16
{"ebwewbebwbbeeeew","wwewebwwweewwewb","beebeewwewbwweee","ewbbeebbewwbeebw","ebbewbwbbweweeww","weeebbeeeeeeebbb","wwebbwwwewebwbeb","weeebwbeewwwwwwe","eewbwbbbweebewbb","bewebbebbwewbwew","wwbwwebbbewwwewb","webewbbwbewewwwe","eebeeeweeweeebwe","ewbwewebewebbebw","eeewewbwewbbebee","bwbwbeewewbewwww","ewbbwwewebeebweb","wwebbebbbewebwew","bbebewwewwbbwwew","ebwwbwwwewbwwbbw"}
Returns: 3
3
6
{"bwwewe","wewwew","eweebe"}
Returns: 2
3
20
{"bbwebbwwweweeebewbww","wwwbeebwweeewwwebbew","weeewbbebewbwbebwwwe"}
Returns: 3
4
8
{"ebwbbweb","eeweeeew","bebbeeeb","webwebwe"}
Returns: 2
11
2
{"ew","bb","be","bw","ew","ee","ww","be","bw","wb","bb"}
Returns: 3
2
7
{"wbbewbe","wwbwbww"}
Returns: 3
14
17
{"wbewwewweewwbbbeb","wwweeeebbwwwwebwb","wbewwbwbbwewewwwb","wwewbwbwwwbbebbwe","beebebbwewebbbeww","bwwwebwwwewwbbbww","wbewbbwbbbbwbwwww","weewbeewwbwbwebwb","wbbbewwwwwwwwewww","eebbbwwbwbbbbwwbw","bbbwwebwwebebbwbe","ewwwwwbeebbewwwee","wweebeewbbbwwwebe","wbbwwwbbwewbbeewb"}
Returns: 3
8
11
{"bbbbwbwbwwb","ewwwwwwewwe","wweewbbbwww","bewwebbbbew","eweebwewwwe","webbewwbweb","bebbebbwwwe","ebbebweweeb"}
Returns: 3
11
14
{"bwbbbbebebwbbb","wbbbbwwbbbwwwe","ewweebeeebbebw","webwbbwewbebww","bwebbbwewwbbee","ewbwwbbbbbbwbw","bweewewwbbbbww","wbebewbbeeeweb","bwebeweebewbwb","ewwbwwbewbwwbw","wewbbwwewbbbbe"}
Returns: 4
18
14
{"ewbwewwwbbbbbb","wbbbeeebwwwwwb","webewbbwbwwbwb","ebwwwwbwwbwweb","bwbbbbbwwbbewe","bbbebbwbbbeewb","wewwbbwwwbewbe","wwewbbebbbwbwb","ebbbwwwbebwebb","eebeweweewbbbw","ewwbwbeebwwbwe","weebbebwwwbwbb","bwwweewbewwwbw","wwbewbbwwebewb","ebwbwwbwbbwbeb","wwbweweewbwwbw","ewbbwbebbwwwbw","wbwebwbbwwebww"}
Returns: 4
17
8
{"wwwewwww","webewbww","bebebbbb","wewewbbw","bwbwwwew","bwewbwbb","ebweewww","wewwbwwb","eewwewee","wweeebbw","ebbwbbwb","ewewbbwe","wbwwbewb","bewebeew","ebebbbew","ewbeebbw","wwebbwee"}
Returns: 4
15
3
{"wbb","wew","wbw","bbw","wew","wbw","bww","eeb","www","wew","web","wbw","web","wbw","bbb"}
Returns: 3
20
5
{"beweb","webwb","wwbww","wbwww","wwbwe","bwbwb","bewwb","bebww","wbwwe","wwebb","wwbwe","bebww","bwwww","wwwwb","bweew","ebbww","eeebe","ewbbb","eebwe","bewww"}
Returns: 3
20
10
{"beeewbbwwb","wwbwwwbewb","eeebwbbbee","wbwbewbewb","wwwebwewwb","wwbwbbbwew","ebwwbwwwbw","ebwbewwebe","wbebwbwwww","ewbbewwbwe","wewbbebweb","eeweewwbew","eeeewewbbw","weebbwwwww","ebwwbweweb","wewewbwbww","bbebwebbwb","weeeeewbwb","wbbbeewbbw","eeewbewwee"}
Returns: 2
3
17
{"bewwwbbbwbwbweebb","bbbbwbbweebewewbw","wbwwwbebwbewwwbww"}
Returns: 5
20
20
{"bwbwbwbwbwbwbwbwbwbw", "wwwwbbbbwwwwbbbbwwbb", "bwbwbwbwbwbwbwbwbwbw", "wwwwbbbbwwwwbbbbwwbb", "bwbwbwbwbwbwbwbwbwbw", "wwwwbbbbwwwwbbbbwwbb", "bwbwbwbwbwbwbwbwbwbw", "wwwwbbbbwwwwbbbbwwbb", "bwbwbwbwbwbwbwbwbwbw", "wwwwbbbbwwwwbbbbwwbb", "bwbwbwbwbwbwbwbwbwbw", "wwwwbbbbweewbbbbwwbb", "bwbwbwbwbwbwbwbwbwbw", "wwwwbbbbwwwwbbbbwwbb", "bwbwbwbwbwbwbwbwbwbw", "wwwwbbbbwwwwbbbbwwbb", "bwbwbwbwbwbwbwbwbwbw", "wwwwbbbbwwwwbbbbwwbb", "bwbwbwbwbwbwbwbwbwbw", "wwwwbbbbwwwwbbbbwwbb" }
Returns: 5