# POJ3276——暴力——Fliptile

http://poj.org/problem?id=3279

```/*

*/
/************************************************
* Author        :Powatr
* Created Time  :2015-8-9 13:18:38
* File Name     :D.cpp
************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

int n, m;
char s[400];
char ss[400];
int  maze[20][20];
int mp[20][20];
int path[20][20];
int f_path[20][20];

int solve(int cnt)
{
int  ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
mp[i][j] = maze[i][j];
for(int i = 1; i <= m; i++){
if(cnt&(1<<(i-1))){
ans++;
path[1][i] ^= 1;
mp[1][i] ^= 1;
mp[1][i-1] ^= 1;
mp[1][i+1] ^= 1;
mp[2][i] ^= 1;
}
}
for(int i = 2; i <= n;i++){
for(int j = 1; j <= m; j++){
if(mp[i-1][j] == 1){
ans++;
path[i][j] ^= 1;
mp[i-1][j] ^= 1;
mp[i][j] ^= 1;
mp[i][j-1] ^= 1;
mp[i][j+1] ^= 1;
mp[i+1][j] ^= 1;
}
}
}
for(int j = 1; j <= m; j++)
if(mp[n][j])
return -1;
return ans;
}

int main(){
while(~scanf("%d%d", &n, &m)){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
scanf("%d", &maze[i][j]);
}
memset(f_path, 0 , sizeof(f_path));
for(int i = 1; i <= n*m ; i++)
ss[i] = ‘1‘;
int min1 = n*m + 1;
for(int i = 0; i <= (1<<n) - 1; i++){
int res = 0;
memset(path, 0, sizeof(path));
memset(mp, 0, sizeof(mp));
int temp = solve(i);
if(temp == -1) continue;
if(temp <= min1) {
min1 = temp;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
s[++res] = (char)(path[i][j] + ‘0‘);
}
}
if(strcmp(s+1, ss+1) < 0){
strcpy(ss+1, s+1);
}
}
}
if(min1 == n*m + 1)
printf("IMPOSSIBLE\n");
else {
for(int i = 1; i <= n*m; i++){
printf("%c%c", ss[i], i % m == 0 ? ‘\n‘ : ‘ ‘);
}
}
}
return 0;
}
```

## poj 3279 Fliptile(二进制暴力)

Fliptile Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 3629   Accepted: 1400 Description Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which

## 1647: [Usaco2007 Open]Fliptile 翻格子游戏

1647: [Usaco2007 Open]Fliptile 翻格子游戏 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 423  Solved: 173[Submit][Status][Discuss] Description Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a

## 【反转】POJ3276

Face The Right Way 题意:N个牛 每个都有一定的方向 B背对 F表示头对着你 给你一个装置 每次可以选择连续的K个牛反转方向 问你如何选择K 使得操作数最少 k也应尽量小. 例子:   N=7   BBFBFBB   (F:前面   B:后面)    (红色的为要反转的)   此出K=3  M=3 B B F B F B B F F B B F B B F F F F B B B F F F F F F F   成功了 如果用暴力的方法的话:   考虑N头牛的话最坏情况下要进行