专栏首页ACM算法日常翻转瓷砖Fliptile(开关反转)- POJ 3279

翻转瓷砖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

概译:输入M×N的表格共黑白两种颜色,其中1代表黑色,0代表白色。当奶牛击中一个格子时,它的上下左右和自己都会翻转成相反颜色。选择最小的翻转次数使得翻转后全是白色,输出每块砖的击打次数。若有多种情况,则选择假定输出为一个字符串时的最小字典序答案。

同样是开关反转的问题,比较经典,与POJ-3276的不同之处是这道题目从线变成了面增加了难度。

思路是位运算的枚举。

可以先枚举出第一行的所有情况,然后对于每一种情况进行以下做法:同一块砖翻过来翻回去是没有意义的,所有每块砖最多敲击一次就行了。我们只要从第二行开始逐个检查,检查第i行第j块时,如果第i-1行的第j块经过判断是黑色的,则翻转一次第i行第j块使其变成白色。这样一遍操作之后,最后再检查一遍最后一行是否都是白色,若有黑色,就没机会翻转了,则这种情况为无解。

另外,对于第一行的枚举,可以从0到(1<<n)-1枚举i,然后对此i(视为二进制)的各位数字(为0或1)进行分别提取放进翻转方案的第一行,就可以得到所有的第一行可能翻转方案。需要对位运算知识稍有了解。

关键在于黑色瓷砖的判断和翻转的记录,详见代码。

#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;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:AlphaWA

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-04-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    ACM算法日常
  • CodeForces 982F:The Meeting Place Cannot Be Changed(有向图)

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

    ACM算法日常
  • Planning mobile robot on Tree (EASY Version)(UVA12569,状态压缩)

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

    ACM算法日常
  • 仿qq最新侧滑菜单

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

    xiangzhihong
  • HDU 5652 India and China Origins(并查集)

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

    ShenduCC
  • 230B. T-primes (数论)

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

    dejavu1zz
  • Android打造不一样的新手引导页面(一)

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

    用户2965908
  • LintCode 交错正负数题目分析代码

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

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

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

    ACM算法日常
  • 【POJ 3176】Cow Bowling(DP)

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

    饶文津

扫码关注云+社区

领取腾讯云代金券