# 翻转瓷砖Fliptile（开关反转）- POJ 3279

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 they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.

As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.

Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word "IMPOSSIBLE".

Input

Line 1: Two space-separated integers: M and N

Lines 2.. M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white

Output

Lines 1.. M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.

Sample Input

4 4

1 0 0 1

0 1 1 0

0 1 1 0

1 0 0 1

Sample Output

0 0 0 0

1 0 0 1

1 0 0 1

0 0 0 0

```#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int dx[5] = {1, -1, 0, 0, 0};
const int dy[5] = {0, 0, 0, 1, -1};

int m, n, ans = -1;
int tile[16][16], flip[16][16], final[16][16];
//tile为初始黑白瓷砖，flip[i][j]=1时为翻转这块瓷砖，final是最终输出

int get(int x, int y) { //判断这块砖被翻转之后是黑是白

int c = tile[x][y]; //本身的原始色

for (int i = 0; i < 5; i++) {

int tx = x + dx[i], ty = y + dy[i];
//只有它周围的五个砖（包括自己）在翻转时才会影响到它的颜色变化
if (tx >= 0 && tx < m && ty >= 0 && ty < n)
c += flip[tx][ty];
}

return c % 2;
}
int cal() {

for (int i = 1; i < m; i++) //第一行预设好了，所以从第二行开始
for (int j = 0; j < n; j++) {

if (get(i - 1, j) != 0) //如果上面那个是黑砖，需要翻转下面这块砖来导致上面翻成白色
flip[i][j] = 1;
}

for (int i = 0; i < n; i++) {
if (get(m - 1, i) != 0) //最后一行还需要翻转的话就无解了
return -1;
}

int res = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
res += flip[i][j]; //共翻转了几次
return res;
}
int main() {
//输入
cin >> m >> n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> tile[i][j]; //1是黑色，0是白色

for (int i = 0; i < 1 << n; i++) { //枚举第一行的所有状态

memset(flip, 0, sizeof(flip)); //每换一种新情况都要重新写flip
for (int j = 0; j < n; j++) {
flip[0][n - 1 - j] = i >> j & 1; //先移位再与1
}

int num = cal();
if (num >= 0 && (ans < 0 || num < ans) ) { //记录最优解
ans = num;
memcpy(final, flip, sizeof(flip));
}

}
//输出
if (ans == -1)
cout << "IMPOSSIBLE" << endl;
else
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
printf("%d%c", final[i][j], j == n - 1 ? '\n' : ' ');

return 0;
}```

0 条评论

• ### 搜索专题3 | 八数码 HDU - 1043

本搜索专题会参考vjudge上的《kuangbin带你飞》系列题目，前面2篇是基础题，后面会慢慢复杂起来！加油！

• ### CodeForces 982F：The Meeting Place Cannot Be Changed（有向图）

Petr is a detective in Braginsk. Somebody stole a huge amount of money from a ba...

• ### Planning mobile robot on Tree (EASY Version)（UVA12569，状态压缩)

题目链接：https://vjudge.net/problem/UVA-12569

• ### 仿qq最新侧滑菜单

为了后续对这个项目进行优化，比如透明度动画、背景图的位移动画，以及性能上的优化。 我把这个项目上传到github上面，请大家随时关注。 github地址 htt...

• ### HDU 5652 India and China Origins（并查集）

India and China Origins Time Limit: 2000/2000 MS (Java/Others)    Memory Limit:...

• ### 230B. T-primes （数论）

We know that prime numbers are positive integers that have exactly two distinct ...

• ### Android打造不一样的新手引导页面（一）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

• ### LintCode 交错正负数题目分析代码

样例 给出数组[-1, -2, -3, 4, 5, 6]，重新排序之后，变成[-1, 5, -2, 4, -3, 6]或者其他任何满足要求的答案

• ### 搜索专题3 | 八数码 HDU - 1043

本搜索专题会参考vjudge上的《kuangbin带你飞》系列题目，前面2篇是基础题，后面会慢慢复杂起来！加油！

• ### 【POJ 3176】Cow Bowling（DP）

The cows don't use actual bowling balls when they go bowling. They each take a n...