題意：給你一個(gè)給你一個(gè)矩陣，有黑白兩個(gè)狀態(tài)。每次你可以選擇一個(gè)變?yōu)槠湎喾吹臓顟B(tài)，它周圍的4個(gè)都會(huì)變成相反的狀態(tài)。問你最少需要改變多少個(gè)使得矩陣中的狀態(tài)全為白色，若有多個(gè)答案，輸出字典序最小的

思路：白書p153

題解：這個(gè)題仍然是個(gè)反轉(zhuǎn)問題,我們只需要枚舉第一行(二進(jìn)制)進(jìn)行翻轉(zhuǎn)的坐標(biāo)， 然后根據(jù)當(dāng)前這塊上面那塊是否是黑色（依據(jù)該塊上面本來是什么以及周圍或者自身總共反轉(zhuǎn)了多少次確定）最后得出該塊是否需要反轉(zhuǎn)， 最后只需要特判最后一行是否合理即全為白色，并進(jìn)行維護(hù)更新答案即可。

另外其實(shí)每個(gè)點(diǎn)最多只會(huì)被翻轉(zhuǎn)一次，因?yàn)槿绻D(zhuǎn)兩次和不翻轉(zhuǎn)是一樣的。

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?Nspace-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 #include<stdio.h> #include<string.h> using namespace std; const int M=110; int m,n; int mp[M][M]; int s[M][M];//保存中間結(jié)果 int w[M][M];///保存最優(yōu)解,s,w，記錄的都是翻動(dòng)操作 int e[5][2]= {0,0,0,1,1,0,-1,0,0,-1};//領(lǐng)接格子的坐標(biāo)包括本身 int f(int x,int y)//查詢（x,y）的顏色判斷該點(diǎn)是否為黑色 {int xx=mp[x][y];for(int i=0; i<5; i++){int u=x+e[i][0],v=y+e[i][1];if(u>=0&&u<m&&v>=0&&v<n)xx+=s[u][v];}return xx%2; } int bfs()//求出第一行確定情況下的最小操作，不存在解的話，返回-1 {int ant=0;for(int i=1; i<m; i++)//求出從第二行開始翻轉(zhuǎn)for(int j=0; j<n; j++)//上方格子是黑色，必須必須反轉(zhuǎn)（i,j）號(hào)格子if(f(i-1,j))s[i][j]=1;for(int i=0; i<n; i++)//判斷最后一行是否全白if(f(m-1,i))return -1;for(int i=0; i<m; i++)//統(tǒng)計(jì)翻轉(zhuǎn)的次數(shù)for(int j=0; j<n; j++)ant+=s[i][j];return ant; } void solve() {int ans=0x3f3f3f3f;for(int i=0; i<(1<<n); i++)//按字典序嘗試第一行的所有可能性{memset(s,0,sizeof(s));for(int j=0; j<n; j++)//給第一行各個(gè)位置是否翻動(dòng)按字典序賦值s[0][n-j-1]=i>>j&1;int num=bfs();if(num>=0&&ans>num){ans=num;memcpy(w,s,sizeof(s));//把dp數(shù)組復(fù)制給s數(shù)組（int數(shù)組的復(fù)制memcpy）}}if(ans==0x3f3f3f3f)printf("IMPOSSIBLE\n");else{for(int i=0; i<m; i++)///輸出翻動(dòng)操作{for(int j=0; j<n-1; j++)printf("%d ",w[i][j]);printf("%d\n",w[i][n-1]);}} } int main() {while(~scanf("%d%d",&m,&n)){memset(w,0,sizeof(w));for(int i=0; i<m; i++)for(int j=0; j<n; j++)scanf("%d",&mp[i][j]);solve();}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的Fliptile POJ - 3279 (翻转)（二进制+对第一行暴力遍历翻转的位置）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。