最近看了一篇讲acm技能树的文章 决定按照上面的顺序刷题
文章链接：https://blog.csdn.net/qq_36345036/article/details/79860808
第一题是一个暴力枚举的题
题目链接：http://poj.org/problem?id=1753
翻译一下就是有一个4*4的棋盘 棋子有黑白两面 w代表白色朝上 b代表黑色朝上
每次翻转一个棋子 可以将它自己和上下左右四个棋子翻转
问把棋盘变成全白或全黑的最少操作个数
分析：
对于一个棋子 只有翻转一次或者翻转0次 因为翻转奇数次和翻转1次相同 翻转2次和翻转偶数次相同
棋盘的大小是确定的4*4 很小 所以我们可以直接枚举 翻转0个 看是否全白或全黑 翻转1个 看是否全白或全黑.............翻转16个 看是否全白或全黑
所以本题的关键 是要找出 不同的棋盘位置的组合 进行判断
而不同的组合 本质上就是求 从n个数中选取m个数的组合数 即Cmn
至于怎么求组合数 我在前一篇文章已经写过了 直接套用就好了
#include <stdio.h> //POJ不支持bits/stdc++.h 真难受QAQ #include <stdlib.h> #include <iostream> #include <string.h> using namespace std; int flag=0,ms[4][4]; void change(int newm[][4],int *b,int m) //翻转 { int i; for(i=0;i<m;i++) { int t=b[i]; int tx=b[i]/4; int ty=b[i]%4; newm[tx][ty]=!newm[tx][ty]; if(tx+1<4) newm[tx+1][ty]=!newm[tx+1][ty]; if(ty+1<4) newm[tx][ty+1]=!newm[tx][ty+1]; if(tx-1>=0) newm[tx-1][ty]=!newm[tx-1][ty]; if(ty-1>=0) newm[tx][ty-1]=!newm[tx][ty-1]; } } int panduan(int newm[][4]) //判断 { int sflag=1,i,j; for(i=0;i<4;i++) for(j=0;j<4;j++) if(newm[i][j]!=newm[0][0]) { return 0; } return 1; } void digui(int *a,int *b,int t,int now,int n,int m) //递归求组合数 { int i,j; if(t==m) { int newm[4][4]; for(i=0;i<4;i++) for(j=0;j<4;j++) newm[i][j]=ms[i][j]; //创建一个棋盘的副本 避免影响原本的棋盘 change(newm,b,m); if(panduan(newm)) flag=1; return; } else { for(i=now;i<=n-(m-t);i++) { b[t]=a[i]; digui(a,b,t+1,i+1,n,m); } } } int main() { int i,j; char m[4][4]; int a[16]={0,2,3,4,5,6,7,8,9,10,11,12,13,14,15,15}; int b[16]; for(i=0;i<4;i++) { cin>>m[i]; for(j=0;j<4;j++) { if(m[i][j]=='w') ms[i][j]=1; else ms[i][j]=0; } } for(i=0;i<=16;i++) { memset(b,0,sizeof(b)); //记得每次都要清零 digui(a,b,0,0,16,i); if(flag==1) { cout<<i<<endl; break; } } if(i==17) cout<<"Impossible"<<endl; }