首页 > 代码库 > 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;}
Code
for(int i = 0;i < (1 << 9);i++){     for(int j = 0;j < 9;j++){         if(i & (1 << j)){        }       }  }        

 

Problem D: Flip Five