棋盤變幻

題目大意：

有一些棋子（黑/白），可以將某一列的棋子顏色反轉，要黑棋盡可能小

原題：

題目描述

小G在一個n*m的棋盤上隨意放上了一些黑色的棋子，然后又在剩下所有沒有放棋子的格子里放上了白色的棋子。現在小G想知道他是否能通過以下兩種變換將整個棋盤上的棋子全部變成白色。
　　變幻1：選擇一列，將這一列的棋子全部反色，即黑變白，白變黑。
　　變幻2：選擇一行，將這一行的棋子全部反色。
　　如果能將整個棋盤上的棋子全部變成白色，則輸出最少需要的變幻次數。否則輸出經過若干次變幻后，棋盤上最少的黑子個數。

輸入

第一行兩個正整數n，m，含義見題面。
接下里n行，每行m個字符，‘0’表示白子，‘1’表示黑子。

輸出

一行一個整數ans，含義見題面。

輸入樣例

3 4 0111 0111 1000

輸出樣例

3

說明

對于30%的數據，1 ≤ n ，m ≤ 9。
對于60%的數據，1 ≤ n ，m ≤ 15。
對于100%的數據，1 ≤ n ≤ 16，1 ≤ m ≤ 20。

解題思路：

用dfs枚舉每一行翻不翻，然后枚舉每一列需不需要翻，然后取最優的就可以了

代碼

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,l,num,sum,ans,minn,a[25][25]; char x; void dfs(int dep,int c) {if (dep>n){l=c;num=0;for (int j=1;j<=m;++j){sum=0;for (int i=1;i<=n;++i)sum+=a[i][j];if (n-sum<sum) sum=n-sum,l++;//要翻num+=sum;//累加}minn=min(minn,num);if (!num) ans=min(ans,l);//記錄return;}for (int j=1;j<=m;++j)a[dep][j]=(a[dep][j]+1)%2;//所有都翻一遍dfs(dep+1,c+1);//翻for (int j=1;j<=m;++j)a[dep][j]=(a[dep][j]+1)%2;//返回來dfs(dep+1,c);//不翻 } int main() {scanf("%d %d",&n,&m);for (int i=1;i<=n;++i){getchar();for (int j=1;j<=m;++j){x=getchar();a[i][j]=x-48;//記錄}}ans=2147483647;minn=2147483647;dfs(1,0);if (!minn) printf("%d",ans);else printf("%d",minn); }

總結

以上是生活随笔為你收集整理的【dfs】棋盘变幻的全部內容，希望文章能夠幫你解決所遇到的問題。

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