• POJ 1753题干DescriptionInputOutputSample InputSample Output思路提交代码 题干 Description Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side...
POJ 1753题干DescriptionInputOutputSample InputSample Output题意思路提交代码
题干
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
题意
有一个4x4的棋盘，放满了黑白子，可以选择翻动任意棋子，翻动时改变该棋子和其上下左右四个棋子的颜色（如果存在的话）。
思路
每个棋子只有翻不翻两种情况，简单的枚举，一共只有65536种情况，每种判断下能不能通过。暴力DFS就能a，注意边界情况的执行顺序别写错就行了。
提交代码
#include <stdio.h>

bool flip[4][4];
int ans = 9999999;

bool panduan(){
bool flag = flip[0][0];
for(int i = 0 ; i < 4 ; i++){
for(int j = 0 ; j < 4 ; j++){
if(flip[i][j] != flag) return false;
}
}
return true;
}

void fan(int x, int y){
flip[x][y] = !flip[x][y];
if(x-1 >= 0) flip[x-1][y] = !flip[x-1][y];
if(x+1 < 4) flip[x+1][y] = !flip[x+1][y];
if(y-1 >= 0) flip[x][y-1] = !flip[x][y-1];
if(y+1 < 4) flip[x][y+1] = !flip[x][y+1];
}

void dfs(int x, int y, int t){
if(panduan()) {
if (t < ans) ans = t;
return;
}

if(y > 3) return;

int nx,ny;

if(x < 3){
nx = x+1;
ny = y;
}else{
nx = 0;
ny = y+1;
}

fan(x,y);
dfs(nx,ny,t+1);
//by wjq
fan(x,y);
dfs(nx,ny,t);
}

bool isWhilt(char c){
if (c == 'w') return true;
else return false;
}

int main(){
for(int i = 0 ; i < 4 ; i++){
for(int j = 0 ; j < 4 ; j++){
flip[i][j] = isWhilt(getchar());
}
getchar();
}
dfs(0,0,0);
if(ans != 9999999)
printf("%d\n",ans);
else
printf("Impossible\n");
return 0;
}




展开全文
• poj 1753 Flip Game 题目 Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 58218 Accepted: 24244 Description Flip game is played on a rectangular 4x4 field with two-sided pieces ...
poj 1753 Flip Game
题目
Flip Game
Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 58218		Accepted: 24244
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).
求解
主要思想： 位运算 ， bfs
首先我们可以将棋盘的状态使用16个bit进行表示。
假设所有的位置都是白色的，则一开始的状态即为0. 对左上角的第一个格子进行反转之后，状态应该为 1100 1000 0000 0000, 即十进制的51200 。我们可以看作0和51200做异或操作，那么我们可以将各个位置反转之后的值都算出来，每次操作通过异或代替。
因为一共只有16个格子，状态个数最多为2的16次方。因此我们需要一个这样大小的数组做遍历标记，防止遍历过程进入循环
从起始状态开始，翻转棋子得到的状态是一个一其实状态为根的16叉树，根据bfs的思想作遍历即可，当得到0或者0xffff时结束，如果全部遍历结束之后仍没有找到则为不可能。


展开全文
• POJ 1753，题目链接http://poj.org/problem?id=1753，翻译一下整个题目的大概意思：有4*4的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑->白或者白->黑)时，其周围上下左右(如果存在的...
http://www.cnblogs.com/shuaiwhu/archive/2012/04/27/2474041.html
POJ 1753，题目链接http://poj.org/problem?id=1753，翻译一下整个题目的大概意思：有4*4的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑->白或者白->黑)时，其周围上下左右(如果存在的话)的格子的颜色也被反转，问至少反转几个格子可以使4*4的正方形变为纯白或者纯黑？

主要思路如下：
1.对于每个格子，它要么反转0次，要么反转1次(当然，它的邻格子也跟着反转)，因为它反转偶数次和反转0次的效果是一样的，同理反转奇数次的效果和反转1次的效果是一样的。2.由于只有16个格子，我们可以选择0个格子，1个格子，2个格子，3个格子......进行反转，总的选择情况为

3.当0个格子被反转时，看它是否为纯色，否则选择一个格子进行反转(有16种选择)，看反转后是否为纯色，否则选择两个格子进行反转(有120种选择)，看反转后是否为纯色......4.只要"3过程"中有纯色出现，就停止"3过程"，输出相应的被选择的格子个数，结束。如果16个格子都被翻转了，还是没变成纯色，则输出“Impossible”。
对于从16个格子中选取n个格子的所有组合，请看前一篇文章从数组中取出n个元素的所有组合（递归实现），这里不再叙述。

1 #include <stdio.h>
2 #include <stdlib.h>
3 //所有都是白的，或者所有都是黑的
4 int all_white_or_black(int* bits, int len)
5 {
6     int i = 0;
7     for (i = 0; i < len - 1; i++)
8         if (bits[i] != bits[i + 1])
9             return 0;
10     return 1;
11 }
12 //改变一个格子的颜色，并根据其所在位置改变其周围格子的颜色
13 void change_color(int* arr, int i)
14 {
15     arr[i] = !(arr[i]);
16     int x = i / 4;
17     int y = i % 4;
18     if (y < 3)
19         arr[i + 1] = !(arr[i + 1]);
20     if (y > 0)
21         arr[i - 1] = !(arr[i - 1]);
22     if (x > 0)
23         arr[i - 4] = !(arr[i - 4]);
24     if (x < 3)
25         arr[i + 4] = !(arr[i + 4]);
26 }
27
28 void combine(int* arr, int len, int* result, int count, const int NUM, int* last)
29 {
30     int i;
31     for (i = len; i >= count; i--)
32     {
33         result[count - 1] = i - 1;
34         if (count > 1)
35             combine(arr, i - 1, result, count - 1, NUM, last);
36         else
37         {
38             int j = 0;
39             //在这里生成arr的副本
40             int* new_arr = (int*)malloc(sizeof(int) * 16);
41             for (j = 0; j < 16; j++)
42                 new_arr[j] = arr[j];
43
44             for (j = NUM - 1; j >= 0; j--)
45             {
46                 change_color(new_arr, result[j]);
47             }
48             if (all_white_or_black(new_arr, 16))
49             {
50                 *last = NUM;
51                 free(new_arr);
52                 break;
53             }
54             free(new_arr);
55         }
56     }
57 }
58
59 int main()
60 {
61     char str[5];
62     int bits[16];
63     int count = 15;
64     int lines = 4;
65     while (lines--)
66     {
67         scanf("%s", str);
68         int i;
69         for (i = 0; i < 4; i++)
70         {
71             if (str[i] == 'b')
72                 bits[count--] = 1;
73             else
74                 bits[count--] = 0;
75         }
76     }
77
78     if (all_white_or_black(bits, 16))
79         printf("%d\n", 0);
80     else
81     {
82         //生成bits数组的副本
83         int* new_bits = (int*)malloc(sizeof(int) * 16);
84         int i;
85         for (i = 0; i < 16; i++)
86             new_bits[i] = bits[i];
87
88         int j;
89         //这里last用来接受combine函数里面的NUM，即需要的步数
90         int last = 0;
91         for (j = 1; j <= 16; j++)
92         {
93             int* result = (int*)malloc(sizeof(int)*j);
94             combine(new_bits, 16, result, j, j, &last);
95             if (last == j)
96             {
97                 printf("%d\n", last);
98                 break;
99             }
100             //new_bits已被改变，所以要还原为bits
101             for (i = 0; i < 16; i++)
102                 new_bits[i] = bits[i];
103
104             free(result);
105         }
106         free(new_bits);
107
108         if (j == 17)
109             printf("Impossible\n");
110     }
111     return 0;
112 }

malloc函数用法
https://blog.csdn.net/linan5231/article/details/50930630
1、函数声明void *malloc(int size);
说明：malloc向系统申请分配size字节的内存空间，返回类型为void*类型。
2、使用int *p;
p = (int *)malloc( sizeof(int) );
注意：
（1）因为malloc返回的是不确定类型的指针，所以返回之前必须经过类型强制转换，否则编译报错，如：“ 不能将void*赋值给int*变量 ”。
（2）malloc只管分配内存，并不会初始化，其内存空间中的值可能是随机的。如果分配的这块空间原来没有被使用过，那么其中每个值都可能是0。相反，空间里面可能遗留各种各样的值。
（3）实参为需要分配的字节大小，如果malloc(1)，那么系统只分配了1个字节的内存空间，这时注意，如果在这块空间中存放一个int值，由于int类型占4个字节，那么还有3个字节未分配空间，系统就会在已经分配的那1个字节的基础上，依次向后分配3个字节空间，而这就占有了“别人”的3个字节空间，“别人”原有的值就被清空了。
（4）分配的空间不再使用时，要用free函数释放这块内存空间。
3、示例分配100个int类型的空间：
int *p;
p = (int *)malloc( sizeof(int) * 100 );
转载于:https://www.cnblogs.com/fengzhongzhuifeng/p/10711859.html
展开全文
• POJ 1753，题目链接http://poj.org/problem?id=1753，翻译一下整个题目的大概意思： 有4*4的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑-&gt;白或者白-&gt;黑)时，其周围上下左右...
水题一道，有多种解法，用的DFS写的，还可以用递归枚举

POJ 1753，题目链接http://poj.org/problem?id=1753，翻译一下整个题目的大概意思：
有4*4的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑->白或者白->黑)时，其周围上下左右(如果存在的话)的格子的颜色也被反转，问至少反转几个格子可以使4*4的正方形变为纯白或者纯黑？

DFS:

#include <stdio.h>

const int inf=9999999;
char s[10];
int map[10][10],i,j;
int ans=inf;

int panduan()
{
int x=map[0][0];
for (i=0; i<4; i++)
{
for (j=0; j<4; j++)
{
if (map[i][j]!=x)
return 0;
}
}
return 1;
}
void fan (int x,int y)
{
map[x][y]=!map[x][y];
if (x - 1 >= 0)
map[x-1][y]=!map[x-1][y];
if (x + 1 < 4)
map[x+1][y]=!map[x+1][y];
if (y - 1 >= 0)
map[x][y-1]=!map[x][y-1];
if (y + 1 < 4)
map[x][y+1]=!map[x][y+1];
}
int dfs (int x,int y,int t)
{
if ( panduan())
{
if (ans > t)
ans = t ;
return 0;
}
if (x >= 4 || y >= 4)
return 0;
int nx,ny;
nx = (x + 1)%4;
ny = y + ( x + 1 ) / 4;

dfs (nx,ny,t);
fan (x,y);

dfs (nx,ny,t+1);
fan (x,y);

return 0;
}

int main ()
{
for (i=0; i<4; i++)
{
scanf ("%s",s);
for (j=0; j<4; j++)
{
if (s[j]=='b')
map[i][j]=0;
else
map[i][j]=1;
}
}
dfs (0,0,0);
if (ans == inf )
printf ("Impossible\n");
else printf ("%d\n",ans);
return 0;
}

使用DFS要考虑时间复杂度，
展开全文

...