TOJ 3248 Flip Game
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:
Choose any one of the 16 pieces.
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).
Consider the following position as an example:
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
Source
因为地图是4*4,每个格子只有2种情况,所以最多的情况只有2^16种。
可以把地图看成:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
从0开始搜索,下面的结点要么翻,要么不翻。记录每次翻完后的黑白棋的数量。如果(黑棋=16 或者 黑棋=0)表示已经达到目的。
#include <stdio.h>
#define inf 0x3f3f3f3f char g[][];
int f[][];
int dir[][]={
{,},{,-},{,},{-,}
};
int ans;
int sum; void change(int x , int y){
f[x][y]=!f[x][y];
for(int i=; i<; i++){
int tx=x+dir[i][];
int ty=y+dir[i][];
if( <=tx && tx< && <=ty && ty<){
f[tx][ty]=!f[tx][ty];
}
}
} void dfs(int h , int step){
if(sum== || sum==){
if(step<ans)
ans=step;
}
if(h>=)return;
//不翻
dfs(h+,step);
//翻
int x=h%;
int y=h/;
int sum1=;
if(f[x][y]){
sum1--;
}else{
sum1++;
}
for(int i=; i<; i++){
int tx=x+dir[i][];
int ty=y+dir[i][];
if( <=tx && tx< && <=ty && ty<){
if(f[tx][ty]){
sum1--;
}else{
sum1++;
}
}
}
change(x,y);
sum+=sum1;
dfs(h+,step+);
sum-=sum1;
change(x,y);
} int main()
{
sum=;
for(int i=; i<; i++){
scanf("%s",g[i]);
}
for(int i=; i<; i++){
for(int j=; j<; j++){
if(g[i][j]=='b'){
f[i][j]=;
sum++;
}
else{
f[i][j]=;
}
}
}
ans=inf;
dfs(,);
if(ans==inf){
printf("Impossible\n");
}else{
printf("%d\n",ans);
}
return ;
}
最新文章
- ZooKeeper集群搭建中的Connection refused而导致的启动失败
- Java中的值传递和引用传递
- 2016.02.17 JS DOM编程艺术 第四五六章
- 如何在PL/SQL Developer 中设置 在select时 显示所有的数据
- NHibernate实例化类部分属性
- poj 3268 Silver Cow Party(最短路)
- POJ 1258 Agri-Net
- C# 调用 MFC DLL
- Spring-----自定义属性编辑器
- mysql学习(九)sql语句
- ubuntu 12.04 x86_64:java.lang.UnsatisfiedLinkError: Could not load SWT library. Reasons
- redis概述(一)
- javascript 自动填充功能
- finecms如何调用多个指定栏目的内容
- 记一次gitlab添加用户收不到邮件的解决办法
- [更新]一份包含: 采用RSA JWT(Json Web Token, RSA加密)的OAUTH2.0,HTTP BASIC,本地数据库验证,Windows域验证,单点登录的Spring Security配置文件
- spring4+springmvc+mybatis基本框架(app后台框架搭建一)
- C++之lambda理解
- MySQL性能优化(二)-- 数据类型,SQL,八种连接
- Android Studio添加assets文件夹