首页 > 代码库 > Problem D: Flip Five
Problem D: Flip Five
大致题意:3 * 3的黑白格,在翻转的时候会本身和四周的都翻转,问最小翻转几次变成全部是白色
解题思路:把3 * 3 = 9 个格子进行全排列,然后穷举然后找翻转的最小次数
#include <iostream>#include <algorithm>#include <cstdio>using namespace std;int dr[] = {0,1,0,-1,0};int dc[] = {0,0,1,0,-1};int a[1000];bool tmp[10][10];void change(int s){ int x = s / 3; int y = s - x * 3; for(int i = 0;i < 5;i++){ int xx = x + dr[i]; int yy = y + dc[i]; if(xx >= 0 && yy >= 0 && xx < 3 && yy < 3) tmp[xx][yy] = !tmp[xx][yy]; }}bool check(){ for(int i = 0;i < 3;i++){ for(int j = 0;j < 3;j++) if(tmp[i][j]) return false; } return true;}int main(){#ifndef ONLINE_JUDGE // freopen("in.in","r",stdin);#endif int t; cin >> t; while(t--){ char str[10][10]; for(int i = 0;i < 3;i++){ cin >> str[i]; } for(int i = 0;i < 1000;i++) a[1000] = 100; int num = 0; for(int i = 0;i < (1 << 9);i++){ int cnt = 0; for(int r = 0;r < 3;r++){ for(int c = 0;c < 3;c++){ if(str[r][c] == ‘*‘) tmp[r][c] = 1; else tmp[r][c] = 0; } } for(int j = 0;j < 9;j++){ if(i & (1 << j)){ change(j); cnt++; } } if(check()){ a[num++] = cnt; } } sort(a,a+num); cout << a[0] << endl; } return 0;}
for(int i = 0;i < (1 << 9);i++){ for(int j = 0;j < 9;j++){ if(i & (1 << j)){ } } }
Problem D: Flip Five
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。