POJ 3279 Fliptile
Description
Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an grid of square tiles, each of which is colored black on one side and white on the other side.
As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.
Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word “IMPOSSIBLE”.
Input
Line : Two space-separated integers: and
Lines : Line describes the colors (left to right) of row of the grid with space-separated integers which are for black and for white。
Output
Lines : Each line contains space-separated integers, each specifying how many times to flip that particular location.
Sample Input
4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
Sample Output
0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0
Translation
有一大块由黑白两色地砖组成的拼图,代表黑色,代表白色。每次翻动一块地砖,都会使该地砖及其周围地砖(有完整的边相接的地砖)颜色改变(黑变白,白变黑)。要求用最少的翻动次数,将所有地砖变成白色,输出每一块地砖被翻动的次数,如果有多种方案,按字典序输出。
Idea
首先,一块地砖翻动奇数次产生的效果是相同的,翻动偶数次相当于没有翻动;因此,如果要翻动一块地砖,该地砖被翻动的次数只需要是。
因此,打印出来的答案就是一个和构成的矩阵,每一行都可以看作是一个二进制数。
事实上,当第行的翻动方案确定后,第行也随之确定(翻动与第行黑地砖相邻的地砖),接着第行也确定……一直递推至第行,这是只需要检查第行是否都是白色地砖,如果是白色地砖,则该方案可行。
枚举第一行的所有方案,若找不到一种可行的方案,就输出"IMPOSSIBLE"。
每一行的翻转情况可以看作一个二进制整数数(一个都不翻转或全部翻转),对于每一个,将其二进制位拆开,如果第位为,则翻转第行第个地砖,题目要求字典序输出,因此第一行的方案要先从开始枚举。接着一直模拟到行,检查行的合法性,若合法,则视情况更新翻动地砖的最小次数和第一行的方案(在枚举中用一个十进制数表示,模拟中拆成二进制数)。
Code
1 |
|