POJ - 3279(枚举+暴力)
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 14297 | Accepted: 5257 |
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".
Input
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
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
Source
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; int m,n; bool right(int i,int j){
if(i>=&&i<m&&j>=&&j<n){
return true;
}else{
return false;
}
} void flip(char grid[][],int i,int j){
int ii=i,jj=j; if(grid[ii][jj]==''){
grid[ii][jj]='';
}else{
grid[ii][jj]='';
} ii=i+,jj=j;
if(right(ii,jj)){
if(grid[ii][jj]==''){
grid[ii][jj]='';
}else{
grid[ii][jj]='';
}
} ii=i-,jj=j;
if(right(ii,jj)){
if(grid[ii][jj]==''){
grid[ii][jj]='';
}else{
grid[ii][jj]='';
}
} ii=i,jj=j+;
if(right(ii,jj)){
if(grid[ii][jj]==''){
grid[ii][jj]='';
}else{
grid[ii][jj]='';
}
} ii=i,jj=j-;
if(right(ii,jj)){
if(grid[ii][jj]==''){
grid[ii][jj]='';
}else{
grid[ii][jj]='';
}
} } int main()
{
char reserve[][];
char grid[][];
char result[][];
char output[][];
int bin[];
scanf("%d %d",&m,&n);
getchar();
for(int i=;i<m;i++){
for(int j=;j<n;j++){
scanf("%c",&reserve[i][j]);
getchar();
}
}
int coun=<<n; int mincou=;
for(int iii=;iii<coun;iii++){ memcpy(grid,reserve,sizeof(reserve));
memset(result,'',sizeof(result)); int cou=;
int t=iii;
int b_i=;
bin[]=; while(t){
bin[b_i]=t%;
t/=;
result[][b_i]=''+bin[b_i];
b_i++;
}
for(int i=;i<n;i++){
if(result[][i]==''){
cou++;
flip(grid,,i);
}
} for(int i=;i<m-;i++){
for(int j=;j<n;j++){
if(grid[i][j]==''){
flip(grid,i+,j);
result[i+][j]='';
cou++;
}
}
}
bool f=true;
for(int i=;i<n;i++){
if(grid[m-][i]==''){
f=false;
break;
}
}
if(f==true){
if(cou<mincou){
mincou=cou;
memcpy(output,result,sizeof(result));
}else if(cou==mincou){
bool flag=true;
for(int i=;i<m;i++){
for(int j=;j<n;j++){
if(output[i][j]>result[i][j]){
break;
}else if(output[i][j]<result[i][j]){
flag=false;
break;
}
}
}
if(flag){
memcpy(output,result,sizeof(result));
}
}
}
} if(mincou==){
printf("IMPOSSIBLE\n");
}else{
for(int i=;i<m;i++){
for(int j=;j<n;j++){
if((i==m-) && (j==n-)){
printf("%c",output[i][j]);
}else{
printf("%c ",output[i][j]);
}
}
if(i!=m-){
printf("\n");
} }
} return ;
}
最新文章
- 【造轮子】打造一个简单的万能Excel读写工具
- [No00009E]几种常见的命名规则
- Java的线程模型
- CentOS6.4 配置Haproxy
- 转 intent常用功能
- 下拉列表框Combo Box
- css table 布局
- Hibernate 系列教程14-继承-PerTable策略
- docker使用Let’s Encrypt协议构建免费https协议
- JSON的数据类型
- laydate时间插件更换皮肤
- 微信客户端+微信公众平台+新浪云SAE+Arduino+WS100(控制LED)
- SublimeText3解决中文乱码
- ASP.NET WebApi OWIN 实现 OAuth 2.0(自定义获取 Token)
- [C++ Primer Plus] 第8章、函数探幽(一)程序清单——内联、引用、格式化输入输出、模板、decltype
- java字符串截取指定下标位置的字符串
- Error running &#39;Unnamed&#39;: Address localhost:1099 is already in use
- Spring -- 自定义转换器
- shell脚本收集服务器基本信息并入库
- 终于在nowcoder爆发了的懒惰
热门文章
- 开源流媒体服务器SRS学习笔记(3) - HTTPCallback实现安全认证
- git 一些常见问题 总结
- Oracle中连接与加号(+)的使用
- Spring Boot 中application.yml与bootstrap.yml的区别
- 通过chrome console 快速获取网页连接
- jsp执行过程图解
- iOS 出现内存泄漏的几种原因
- linux 设备驱动概述
- [k8s]Docker 用户使用 kubectl 命令指南-unkown排错(kubelet端口解析)
- LZW算法PHP实现方法 lzw_decompress php