刷题集——POJ 2179 Fliptile（枚举+模拟）

我不是女神ヾ 2022-12-26 08:16 118阅读 0赞

### [Fliptile][] ###

Time Limit: 2000MS Memory Limit: 65536K  
Total Submissions: 28860 Accepted: 10139  
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 M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) 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 1: Two space-separated integers: M and N  
Lines 2…M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white  
Output

Lines 1…M: Each line contains N 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

--------------------

#### 解题思路：枚举+模拟 ####

**①、假设我们能够确定第一行翻转的情况。**

**②、从第二行第一列开始按照从左到右、从上到下的顺序，依次判断每个方格是否进行翻转。**  
（判断条件：若同列而且上一行的方格为黑则翻转该方格）

**③、检测最后一行是否全部为白，若为白则该翻转方案可行，输出翻转方案。否则改变第一行的翻转情况，重复① ~ ③。**

**④、第一行的全部情况都枚举完了，确定无法将全部方格翻转为白色，输出 IMPOSSIBLE 。**

--------------------

#### 样例说明 ####

①、确定第一行的翻转情况，全部不翻转。  
![1][]  
②、判断第二行的各个方格的翻转情况，按照从左到右判断。  
（判断条件：若同列而且上一行的方格为黑则翻转该方格）  
![2][]  
③、判断第三行的各个方格的翻转情况，按照从左到右判断。  
（判断条件：若同列而且上一行的方格为黑则翻转该方格）  
![3][]  
④、判断第四行的各个方格的翻转情况，按照从左到右判断。  
（判断条件：若同列而且上一行的方格为黑则翻转该方格）  
![4][]  
⑤、检测当前方格情况的最后一行是否全为白色。很幸运，当第一行不翻转时就能将全部方格翻转为白色，输出翻转方案。

--------------------

#### AC代码 ####

#include<iostream>
    #include<memory.h>
    using namespace std;
    bool mm[20][20];
    
    int x[5] = { 0, 0, 0, 1, -1};
    int y[5] = { 0, -1, 1, 0, 0};
    
    int main(){ 
    	int m, n;
    	cin>>m>>n;
    	for(int i=1; i<=m; i++)
    	for(int j=1; j<=n; j++)
    		cin>>mm[i][j];
    	
    	int flag;
    	//二进制枚举第一行的情况
    	for(int t=0; t<(1<<n); t++){ 	
    		int ans[20][20];
    		bool ma[20][20];
    		memcpy(ma, mm, sizeof(mm));
    		//枚举第一行情况 
    		for(int j=1; j<=n; j++){ 
    			if((t>>(j-1))&1){ 
    				for(int k=0; k<5; k++){ 
    					int di = 1+x[k];
    					int dj = j+y[k];
    					if(di>0&&dj>0&&di<=m&&dj<=n)
    						ma[di][dj] = !ma[di][dj];
    				}
    				ans[1][j] = 1;
    			}
    			else
    				ans[1][j] = 0;
    		}
    	
    		//检测当前情况是否符合 
    		for(int i=2; i<=m; i++)
    		for(int j=1; j<=n; j++){ 
    			if(ma[i-1][j]){ 
    				for(int k=0; k<5; k++){ 
    					int di = i+x[k];
    					int dj = j+y[k];
    					if(di>0&&dj>0&&di<=m&&dj<=n)
    						ma[di][dj] = !ma[di][dj];
    				}
    				ans[i][j] = 1;
    			}
    			else
    				ans[i][j] = 0;
    		}
    		
    		flag=0;
    		for(int j=1; j<=n; j++)
    			if(ma[m][j]) flag=1;
    			
    		if(!flag){ 
    			for(int i=1; i<=m; i++){ 
    				for(int j=1; j<=n; j++){ 
    					cout<<ans[i][j];
    					if(j!=n) cout<<" ";
    				}
    				cout<<"\n";
    			}
    			break;
    		}
    	}
    	if(flag)
    		cout<<"IMPOSSIBLE\n";
    	
    	return 0;
    }

--------------------

#### 总结 ####

题目难点：在各方格翻转会影响周围方格的条件下，将全部方格翻转为白色同时还存在不可能的情况。

暴力枚举------复杂度 O( 2M\*N )  
枚举+模拟----复杂度 O( M \* 2N )

枚举+模拟的巧妙之处：抓住了行与行之间的关系，通过枚举第一行的情况，有效的避免所有可翻转成功的情况被遗漏，实在巧妙。

出题人、解题人：就很强、就很无敌

[Fliptile]: http://poj.org/problem?id=3279
[1]: /images/20221120/aab591bb34574281872a21f859dd2378.png
[2]: /images/20221120/13cab2292f844310a742db81a4b0dcc2.png
[3]: /images/20221120/95f269c2949b433ea68e9a4776310efa.png
[4]: https://img-blog.csdnimg.cn/20201203194648140.png