POJ 3279 Fliptile(翻格子)
Time Limit: 2000MS Memory Limit: 65536K
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 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".
农夫John知晓了一只智商不堪忧的快乐奶牛产出更多。于是他用广场砖弄了个M × N ( ≤ M ≤ ; ≤ N ≤ )的网格,一面黑一面白,用来玩智力游戏。 如你所想,白的翻过来是黑的,黑的翻过来是白的。如果奶牛翻转瓷砖,使所有白面朝上,则会得到奖励。然而牛蹄子大,翻一块砖时会联动翻转相邻的砖(与被翻转的砖共享边缘)。翻面很累牛,因此他们想尽可能少翻点。 帮助奶牛们确定最少的翻转次数,还有最少需要翻动的位置。如果存在多解,则选取输出字符串字典序最小的解法。如果无解,则输出一行 "IMPOSSIBLE"。
CN
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
第1行:两个以空格分隔的整数:M和N
第2..M+1行:第i+1行是从左到右地描述第i行网格的颜色,有N个由空格分隔的整数,1表示黑,0表示白。
CN
Output - 输出
Lines 1..M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.
第1..M行:每行有N个由空格分隔的整数,每个数表示当前位置需要翻转的次数。
CN
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
题解
题目的最少翻转次数不明觉厉,字典序的描述也是感觉有点问题,曾让我误以为策略是需要从左往右一列一列地搜索。主要还是道考(cai)策略的题目…………
看着样例感觉翻转没有顺序的区别,那就从下往上地看(一开始看列看发现输出不对),一行一行地看,从左往右,从上往下。
因为感觉没有顺序差别,所以翻转最多一次,翻两次回到原点。
下面的行可以为上面的行做最终决定,依次往下,就看最后一行是否为0即可判断是否成立。
唯一没法决定的在第一行,因此需要枚举第一行的开场情况,枚举第一行翻的位置与翻的次数(二进制)。
一开始也是对这个策略将信将疑,然后强迫症发作找到这个游戏,玩了几把后就差不多有自信写了……
(Flash好像加载不出来,这里直接放链接好了)http://s1.4399.com:8080/4399swf/upload_swf/ftp/20080527/1.swf
代码 C++
#include <cstdio>
#include <cstring>
int row[], rowBack[], ts[], bit[], m, n;
void reRow(int y, int x){
if (y < || x < || y >= m || x >= n) return;
row[y] ^= bit[x];
}
void opt(){
int i, j;
for (i = ; i < m; ++i){
printf("%d", ts[i] & bit[]);
for (j = ; j < n; ++j) printf(" %d", (ts[i] & bit[j]) >> j);
puts("");
}
}
int main(){
int i, j, k, ed;
for (i = , j = ; i < ; ++i, j <<= ) bit[i] = j;
scanf("%d%d", &m, &n);
for (i = ; i < m; ++i){
for (j = ; j < n; ++j){
scanf("%d", &k);
if (k) rowBack[i] ^= bit[j];
}
} for (i = , ed = << n; i < ed; ++i){
memcpy(row, rowBack, sizeof rowBack);
memset(ts, , sizeof ts); ts[] = i;
for (j = ; j < n; ++j){
if (i & bit[j]){
reRow(, j); reRow(, j - ); reRow(, j + ); reRow(, j);
}
}
for (j = ; j < m; ++j){
for (k = ; k < n; ++k){
if (row[j - ] & bit[k]){
reRow(j - , k); reRow(j + , k); reRow(j, k); reRow(j, k - ); reRow(j, k + );
ts[j] ^= bit[k];
}
}
}
if (!row[m - ]) break;
}
if (row[m - ]) puts("IMPOSSIBLE");
else opt();
return ;
}
POJ 3279 Fliptile(翻格子)的更多相关文章
-
1647: [Usaco2007 Open]Fliptile 翻格子游戏
1647: [Usaco2007 Open]Fliptile 翻格子游戏 Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 423 Solved: 173[ ...
-
[Usaco2007 Open]Fliptile 翻格子游戏
[Usaco2007 Open]Fliptile 翻格子游戏 题目 Farmer John knows that an intellectually satisfied cow is a happy ...
-
Fliptile 翻格子游戏
问题 B: [Usaco2007 Open]Fliptile 翻格子游戏 时间限制: 5 Sec 内存限制: 128 MB 题目描述 Farmer John knows that an intell ...
-
[BZOJ 1647][USACO 2007 Open] Fliptile 翻格子游戏
1647: [Usaco2007 Open]Fliptile 翻格子游戏 Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 702 Solved: 281[ ...
-
POJ.3279 Fliptile (搜索+二进制枚举+开关问题)
POJ.3279 Fliptile (搜索+二进制枚举+开关问题) 题意分析 题意大概就是给出一个map,由01组成,每次可以选取按其中某一个位置,按此位置之后,此位置及其直接相连(上下左右)的位置( ...
-
状态压缩+枚举 POJ 3279 Fliptile
题目传送门 /* 题意:问最少翻转几次使得棋子都变白,输出翻转的位置 状态压缩+枚举:和之前UVA_11464差不多,枚举第一行,可以从上一行的状态知道当前是否必须翻转 */ #include < ...
-
[Usaco2007 Open]Fliptile 翻格子游戏题解
问题 B: [Usaco2007 Open]Fliptile 翻格子游戏 时间限制: 5 Sec 内存限制: 128 MB 题目描述 Farmer John knows that an intell ...
-
POJ 3279(Fliptile)题解
以防万一,题目原文和链接均附在文末.那么先是题目分析: [一句话题意] 给定长宽的黑白棋棋盘摆满棋子,每次操作可以反转一个位置和其上下左右共五个位置的棋子的颜色,求要使用最少翻转次数将所有棋子反转为黑 ...
-
POJ 3279 Fliptile (二进制+搜索)
[题目链接]click here~~ [题目大意]: 农夫约翰知道聪明的牛产奶多. 于是为了提高牛的智商他准备了例如以下游戏. 有一个M×N 的格子,每一个格子能够翻转正反面,它们一面是黑色,还有一面 ...
随机推荐
-
玩转spring boot——结合jQuery和AngularJs
在上篇的基础上 准备工作: 修改pom.xml <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi=&q ...
-
python logging模块 basicConfig配置文件
logging.basicConfig(level=log_level, format='%(asctime)s %(filename)s[line:%(lineno)d] %(levelname)s ...
-
BIP_开发案例04_通过BI Publisher实现打印报表的二维码(案例)(待整理)
2014-01-01 Created BaoXinjian
-
java dump
注意,请不要被我误导,我没有看其他资料,这是我自己分析的,有些可能是不对的 "DestroyJavaVM" prio=6 tid=0x00316800 nid=0x448 wait ...
-
Linux应用程序打包
原文地址:http://blog.solrex.cn/articles/packaging-1-src.html1. 应用程序打包技术之一(源代码篇) 相信很多朋友都曾经为方便做某件事写过自己的小 ...
-
(转)Java线程:线程的同步与锁
Java线程:线程的同步与锁 一.同步问题提出 线程的同步是为了防止多个线程访问一个数据对象时,对数据造成的破坏. 例如:两个线程ThreadA.ThreadB都操作同一个对象Fo ...
-
设计模式 | 原型模式(prototype)
定义: 用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象. 结构:(书中图,侵删) 一个申明克隆自己的接口 若干具体的需要克隆自己的类 这个结构很简单,而且在Java中那个接口是不需 ...
-
Linux下使用Quagga(Zebra)搭建路由器记录(转)
写在前面 从22号中午开始琢磨zebra/quagga的用法,一直到晚上11点多都没有什么头绪.各种Google,百度,几近崩溃.由于网上关于zebra/quagga的配置方法都是在真实的若干台电脑上 ...
-
php通过mysqli链接mysql数据库
首先,我们先来了解一下mysqli是什么,和mysql有什么区别? 1.mysqli是一个扩展库,是允许用户访问mysql4.1或更高版本所提供的功能: 1)mysqli连接是永久连接,而MySQL是 ...
-
算法(1)K-diff Pairs in an Array
写在前面:研究操作系统,习惯了用C,但是在做算法题甚至构建大型系统时,C真的是噩梦.还是用C++比较好,基本算法很成熟,并可基于此实现更复杂的算法.那就边写算法边捡起来好久不用的C++吧! 题目:数组 ...