poj1753

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
", 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
", 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
");
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 );