Flip Game (高斯消元 || dfs)
2024-10-18 22:38:33
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).
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
#include<stdio.h>
#include<string.h>
int c[][]= {,,,,-,,,-,,},min1,t;
char Map[][]; void turn(int x,int y)//改变状态;
{
for(int i=; i<; i++)
{
int dx=x+c[i][];
int dy=y+c[i][];
if(dx<||dy<||dx>=||dy>=)continue;
if(Map[dx][dy]=='b')
Map[dx][dy]='w';
else Map[dx][dy]='b';
}
} int check()//检查是否达到目标状态;
{
int i,j;
for(i=; i<; i++)
for(j=; j<; j++)
if(Map[i][j]!=Map[][])
return ;
return ;
} void dfs(int x,int y,int s)
{
if(check())//检查是否达到目标状态;
{
if(s<min1)//更新结果;
min1=s;
return ;
}
if(x==)return ;
turn(x,y);//改变状态/回溯
//翻转;
if(y==)dfs(x+,,s+);//换行;
else dfs(x,y+,s+);
//不翻转;
turn(x,y);//改变状态/回溯
if(y==)dfs(x+,,s);
else dfs(x,y+,s);
} int main()
{
int i;
min1=;
for(i=; i<; i++)
scanf("%s",Map[i]);
dfs(,,);
if(min1<=)
printf("%d\n",min1);
else printf("Impossible\n");
}
// 高斯消元
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define INF 0x3f3f3f3f
int Map[][] , a[] , min1 , x[] , freex[] ;
char str[][] ;
void getMap(int k)
{
int i , j ;
memset(Map,,sizeof(Map)) ;
for(i = ; i < ; i++)
{
for(j = ; j < ; j++)
{
a[i*+j] = (str[i][j] - '') ^ k ;
Map[i*+j][i*+j] = ;
if( i > )
Map[i*+j][i*+j-] = ;
if( i < )
Map[i*+j][i*+j+] = ;
if( j > )
Map[i*+j][i*+j-] = ;
if( j < )
Map[i*+j][i*+j+] = ;
}
}
return ;
}
void swap1(int p,int q)
{
int j , temp ;
temp = a[p] ;
a[p] = a[q] ;
a[q] = temp ;
for(j = ; j < ; j++)
{
temp = Map[p][j] ;
Map[p][j] = Map[q][j] ;
Map[q][j] = temp ;
}
return ;
}
int solve()
{
int i , j , k , t = , num1 = ;
for(i = ; i < && t < ; t++ , i++)
{
for(j = i ; j < ; j++)
if( Map[j][t] )
break ;
if( j == )
{
freex[num1++] = t ;
i-- ;
continue ;
}
if( i != j )
swap1(i,j) ;
for(j = i+ ; j < ; j++)
{
if( Map[j][t] )
{
a[j] = a[j]^a[i] ;
for(k = t ; k < ; k++)
Map[j][k] = Map[j][k] ^ Map[i][k] ;
}
}
}
for( ; i < ; i++)
if( a[i] )
return - ;
if( num1 ) return num1 ;
for(i = ; i >= ; i--)
{
x[i] = a[i] ;
for(j = i+ ; j < ; j++)
x[i] = x[i]^(Map[i][j]*x[j]) ;
}
return num1 ;
}
int f(int s)
{
int i , j , k , key , ans , min1 = INF ;
getMap(s) ;
key = solve() ;
ans = ;
if( key == )
{
ans = ;
for(i = ; i < ; i++)
ans += x[i] ;
min1 = min(min1,ans) ;
}
else if( key > )
{
int temp = <<key ;
for(int t = ; t < temp ; t++)
{
memset(x,,sizeof(x)) ;
ans = ;
for(j = ; j < key ; j++)
if( t & (<<j) )
{
x[ freex[j] ] = ;
ans++ ;
}
for(i = ; i >= ; i--)
{
for(k = ; k < ; k++)
if( Map[i][k] )
break ;
x[k] = a[i] ;
for(j = k+ ; j < ; j++)
x[k] ^= (Map[i][j]*x[j]) ;
ans += x[k] ;
}
min1 = min(min1,ans) ;
}
}
return min1 ;
}
int main()
{
int i , j , min1 = INF , k , ans , temp ;
for(i = ; i < ; i++)
{
scanf("%s", str[i]) ;
for(j = ; j < ; j++)
{
if( str[i][j] == 'b' )
str[i][j] = '' ;
else
str[i][j] = '' ;
}
}
ans = f() ;
min1 = min(min1,ans) ;
ans = f() ;
min1 = min(min1,ans) ;
if( min1 == INF )
printf("Impossible\n") ;
else
printf("%d\n", min1) ;
return ;
}
最新文章
- (转)C#根据当前时间获取周,月,季度,年度等时间段的起止时间
- Cesium原理篇:2最长的一帧之网格划分
- Laravel 数据库读写分离
- poj3461 Oulipo(KMP模板)
- 参数化命令相关知识点(防止Sql注入)
- 动手学习TCP: 环境搭建
- BZOJ 1071 [SCOI2007]组队
- RabbitMQ-优先级(priority)队列/消息
- python字符串的encode和decode
- Linux c 内存高速访问
- PAT1008
- (原创)Maven+Spring+CXF+Tomcat7 简单例子实现webservice
- winform利用委托delegate进行窗体间通信,相同标题已经存在??
- linux_文件类型
- nginx——location匹配流程图
- CCF CSP 201812-1 小明上学
- WINDOWS下nginx实现本地支持的图片服务器反向代理
- 饮冰三年-人工智能-Python-14Python基础之变量与函数
- Aizu0121 Seven Puzzle(bfs+康托展开)
- 02-OpenLDAP配置
热门文章
- c 时间转移函数
- 教你如何让数据库支持emoji表情符存储
- minicom for Mac 配置
- Mixed Content: xxx This request has been blocked; the content must be served over HTTPS.
- linux 的基本操作(编写shell 脚本)
- ubuntu apt 软件源的更改
- SecureCRT操作指令
- git从已有分支拉新分支开发
- F#周报2019年第3期
- 学习 ASP.NET Core 2.1:集成测试中使用 WebApplicationFactory