題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)n*m的01矩陣，為了好描述，我們?cè)O(shè)0和1是兩個(gè)相反的狀態(tài)，我們的目標(biāo)是要將整個(gè)矩陣全部變成1，現(xiàn)在我們可以將某一個(gè)點(diǎn)(x,y)更改為相反的狀態(tài)，不過(guò)相應(yīng)的該點(diǎn)周?chē)乃膫€(gè)點(diǎn)(x+1,y),(x-1,y),(x,y+1),(x,y-1)也都需要變?yōu)槠浔旧硐喾吹臓顟B(tài)，問(wèn)若想要滿足條件最少需要操作多少次，并輸出方案

題目分析：今天看大藍(lán)書(shū)位運(yùn)算的時(shí)候看到了一個(gè)簡(jiǎn)單版本的題目，直接給秒了，不過(guò)癮，想起來(lái)之前在poj上做過(guò)一個(gè)很類(lèi)似的稍難點(diǎn)的題目，也就是現(xiàn)在這道了，當(dāng)時(shí)卡了我好久，最后還是面向題解編程才寫(xiě)出來(lái)的，現(xiàn)在再回顧一下這給題目直接就給秒了，感覺(jué)真的太爽啦

回到這個(gè)題目上，若我們固定了第一行之后(不能再改變第一行了)，則滿足題意的方案至多只有1種，其原因是：當(dāng)?shù)趇行某一位為0時(shí)，若前i行已經(jīng)被固定，只能點(diǎn)擊第i+1行該位置上的數(shù)字才能使第i行的這一位變?yōu)?，從上到下按照行依次傳遞就能得到方案了，又因?yàn)閚和m最大只有15，我們可以直接對(duì)列狀態(tài)壓縮，首先枚舉第一行的所有狀態(tài)，至多有2^m次方種情況，其中二進(jìn)制中的1表示翻轉(zhuǎn)該方塊，0表示不翻轉(zhuǎn)該方塊，當(dāng)確定好第一行的狀態(tài)后，不斷向下傳遞狀態(tài)就好了，判斷一下最后一行的狀態(tài)能不能滿足條件，若可以的話嘗試更新最小值，并用一個(gè)數(shù)組記錄一下答案，最后輸出答案就好了，總的時(shí)間復(fù)雜度是n*2^m，這個(gè)題目為了迎合題意以及簡(jiǎn)化操作，自己寫(xiě)了不少函數(shù)，用起來(lái)還是挺方便的

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int n,m;int maze[20][20],temp[20][20],temp2[20][20],ans[20][20]; //maze:維護(hù)初始矩陣 temp:每次處理時(shí)暫時(shí)用到的副本矩陣 temp2:記錄每次答案用的 ans:記錄最小值的答案void _copy(int s[][20],int t[][20])//將t數(shù)組復(fù)制給s數(shù)組 {for(int i=0;i<n;i++)for(int j=0;j<m;j++)s[i][j]=t[i][j]; }bool check(int a[])//檢查某一行的狀態(tài)是否全部為1 {for(int i=0;i<m;i++)if(a[i])return false;return true; }void solve(int a[][20],int x,int y)//改變當(dāng)前方塊以及四周方塊的狀態(tài) {a[x][y]^=1;if(x-1>=0)a[x-1][y]^=1;if(y-1>=0)a[x][y-1]^=1;if(x+1<20)a[x+1][y]^=1;if(y+1<20)a[x][y+1]^=1; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&maze[i][j]);int mmin=inf;//維護(hù)最小方案數(shù)for(int i=0;i<1<<m;i++)//枚舉2^m種情況{int cnt=0;//記錄當(dāng)前方案數(shù)_copy(temp,maze);memset(temp2,0,sizeof(temp2));for(int j=0;j<m;j++)//維護(hù)第一行{if(i>>j&1){solve(temp,0,j);temp2[0][j]=1;cnt++;}}for(int i=1;i<n;i++)//逐層向下轉(zhuǎn)移狀態(tài)for(int j=0;j<m;j++){if(temp[i-1][j]){solve(temp,i,j);temp2[i][j]=1;cnt++;}}if(check(temp[n-1]))//檢查最后一行{if(mmin>cnt)//嘗試更新最小值{mmin=cnt;_copy(ans,temp2);}}}if(mmin==inf)printf("IMPOSSIBLE\n");else{for(int i=0;i<n;i++){printf("%d",ans[i][0]);for(int j=1;j<m;j++)printf(" %d",ans[i][j]);printf("\n");}}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 3279 Fliptile(状态压缩+位运算+暴力)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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