最新消息:点击查看大S的省钱秘笈

POJ 1753 Flip Game C++版

POJ题解 Slyar 154浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

帮朋友A的,广搜+位运算

Description

Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:

1. Choose any one of the 16 pieces.
2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).

bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:

bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.

Input

The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.

Output

Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).

Sample Input

bwwb
bbwb
bwwb
bwww

Sample Output

4

Slyar:每次改变相邻位置,求最少步数到全部一样。这种矩阵求最少步数到某一状态一般是考虑BFS了,然后就是怎么简化题目的问题,反正就w和b这2个状态,0和1也是2个状态,所以很容易想到了位运算,16个位置看成16个2进制位就好(目的就是全1或全0),题目要求相邻位置改变,最近看MFC的我马上想到了逻辑操作符...这里的情况是反转,所以用异或...所以算法就很容易了,提前打表求出每一位相邻位置改变后的值(把该位置连同相邻置1,其余位置置0),然后BFS就行了,具体看注释....好久不写ACM程序了,编译错误了3次,数组越界了3次...=_=

转载请注明:Slyar Home » POJ 1753 Flip Game C++版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (6)

  1. @HuaiBoy 你是初中生?
    free斩5年前 (2012-05-10)回复
  2. @kis2009dsh 能把高斯消元的做法发给我看下吗?
    qiqijianglu5年前 (2011-10-06)回复
  3. 今天在百度搜软考中级的网络,来到了这里。。。然后做poj上的题,又到了这里 我觉得这还没什么,我想换个系统 所以要了解一下Linux,结果又到了这里!!!!你是不是交钱给百度了啊。。。。o(╯□╰)o 膜拜Slyar哥
    Paradise5年前 (2011-07-30)回复
  4. 恩,听说高斯消元可以做到0ms,但是还不会啊……………………@kis2009dsh
    匿名6年前 (2011-05-18)回复
  5. 貌似。。。模2域上的高斯消元也行。。。
    kis2009dsh6年前 (2011-01-31)回复
  6. 膜拜Orz 南哥。。。 POJ上的英文题我都无视掉,初中英语还不够应付啊。
    HuaiBoy6年前 (2010-10-30)回复