P1985 翻轉棋

題目描述

農夫約翰知道，聰明的奶?？梢援a更多的牛奶。他為奶牛設計了一種智力游戲，名叫翻轉棋。

翻轉棋可以分成 M × N 個格子，每個格子有兩種顏色，一面是黑的，一面是白的。

一旦翻轉某個格子，這個格子的顏色就會顛倒。如果把所有的格子都翻成白的，就算奶牛贏

了。然而，奶牛的蹄子很大，一旦它們打算翻轉某個格子，這個格子附近（即和這個格子有

公共邊）的格子也會被翻轉。一直翻來翻去也很無聊，奶牛們想最小化必須翻動的次數。

請幫助奶牛確定翻動的最少次數和具體的翻法。如果最小解有多個，則輸出在字典序意義下

最小的那個，如果不可能完成任務，則只要輸出一行單詞：IMPOSSIBLE。

輸入輸出格式

輸入格式：

?

第 1 行：兩個整數：M 和 N

第 2 ~ M+1 行：第 i+1 行從左到右依次描述了棋盤第 i 行的顏色，共 N 個整數。 1 代

表黑色， 0 代表白色。

?

輸出格式：

?

第 1 ~ M 行：每行 N 個整數，分別表示在各個格子上翻轉的次數。

?

輸入輸出樣例

輸入樣例#1：?復制
4 4? 1 0 0 1? 0 1 1 0? 0 1 1 0? 1 0 0 1 輸出樣例#1：?復制
0 0 0 0? 1 0 0 1? 1 0 0 1? 0 0 0 0

說明

·1 ≤ M, N ≤ 15

思路：搜索

由于第一行的修改方案確定之后，每一行的修改方案就確定了，所以說我們只需要用dfs枚舉第一行的修改方案。

而接下來的行數修改的最佳方案是將為1的數的正下方的數進行修改，這樣的好處是每行處理完只需要考慮下一行，不需要考慮以上的行數。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m; int f[1001][1001],ans[1001][1001],cz[1001][1001],a[1001][1001]; int minn=1000000009; void dfs(int lie){ if(lie>m){for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cz[i][j]=a[i][j];for(int i=1;i<=m;i++) if(f[1][i]){ cz[1][i]^=1;cz[2][i]^=1; cz[1][i+1]^=1;cz[1][i-1]^=1; } for(int i=2;i<=n;i++) for(int j=1;j<=m;j++){ if(cz[i-1][j]==1){ f[i][j]=1;cz[i][j]^=1; cz[i][j+1]^=1;cz[i][j-1]^=1; cz[i+1][j]^=1;cz[i-1][j]^=1;} else f[i][j]=0;} bool pd=false;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(cz[i][j]){pd=true; break; }if(!pd){int sum=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(f[i][j]) sum++;if(sum>=minn) return;minn=sum;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) ans[i][j]=f[i][j];}return;}for(int i=0;i<=1;i++){ f[1][lie]=i;dfs(lie+1);} } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];dfs(1);if(minn==1000000009){cout<<"IMPOSSIBLE";return 0;}for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cout<<ans[i][j]<<" "; cout<<endl;} } /* 4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 */

?

轉載于:https://www.cnblogs.com/cangT-Tlan/p/7711345.html

總結

以上是生活随笔為你收集整理的洛谷 P1985 翻转棋的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。