首页 > 代码库 > poj 3279（暴力）
poj 3279（暴力）
题意：有一个n*m的格子，每个格子都有黑白两面（0表示白色，1表示黑色）。我们需要把所有的格子都反转成黑色，每反转一个格子，它上下左右的格子都会跟着反转。请求出用最小步数完成反转时每个格子反转的次数。有多个解时，输出字典序最小的一组。
思路就是先判断第一行，然后如果第一行确定了，那么第二行就必须确定了（如果第一行某个是黑色的，那么必定要在第二行给它翻过来），所以一直到底m-1行都是确定的，接下来只要判断第m行是否是全白就好了。直接枚举第一行就可以，代码是我参考大神的代码写的，里面的二进制枚举操作还是看了有一会儿才看懂
#include <iostream>#include <stdio.h>#include <string.h>using namespace std;const int N = 20;int gh[N][N];//初试的数组int ch[N][N];//操作的数组int vis[N][N];//记录翻过的牌子int re[N][N];//int ans[N][N];//记录答案int fNum,aNum,n,m;void solve( int i,int j ){ fNum++;//操作次数+1 vis[i][j] = 1; ch[i][j] = 1 - ch[i][j]; ch[i-1][j] = 1 - ch[i-1][j]; ch[i][j-1] = 1 - ch[i][j-1]; ch[i+1][j] = 1 - ch[i+1][j]; ch[i][j+1] = 1 - ch[i][j+1];}void record(){ aNum = fNum;//最小次数记录一下 for( int i = 1; i <= m; i++ ){ for( int j = 1; j <= n; j++ ){ ans[i][j] = vis[i][j]; } }}int main(){ cin >> m >> n; for( int i = 1; i <= m; i++ ){ for( int j = 1; j <= n; j++ ){ cin >> gh[i][j]; } } aNum = 10010; int t = 1 << n; for( int loop = 0; loop < t; loop++ ){ for( int i = 1; i <= m; i++ ){ for( int j = 1; j <= n; j++ ){ ch[i][j] = gh[i][j]; } } memset(vis,0,sizeof(vis)); fNum = 0;//记录需要操作的数目 int moveN = loop;//这里是二进制，二进制 for( int i = 1; i <= n; i++ ){ if( moveN&1 ){//这里我看了很久才看明白 //假入一个数字的二进制是0101，意思就是 //第一格翻，第三格翻，上面t为2的N次方，包括了所有的 //可能性的二进制对应的数字 solve( 1,i ); } moveN >>= 1; } for( int i = 2; i <= m; i++ ){ for( int j = 1; j <= n; j++ ){ if( ch[i-1][j] ){//如果上一行是黑色，就处理这一行 solve(i,j); } } } bool flag = true; for( int j = 1; j <= m; j++ ){ if( ch[m][j] ){//直接判断最后一行是否满足 flag = false; break; } } if( flag and fNum < aNum ){ record(); } } if( aNum == 10010 ){ cout << "IMPOSSIBLE\n"; return 0; }else{ for( int i = 1; i <= m; i++ ){ cout << ans[i][1]; for( int j = 2; j <= n; j++ ){ cout << " " << ans[i][j]; } cout << endl; } }}
poj 3279（暴力）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。