此提一共有三种解法：
1.枚举
最朴素的算法，但是一开始我居然不知道如何来枚举。大概的原理是：以位置1,1开始变化。得到16种位置的最小解法，然后选最少的一个就OK。
2.BFS
一开始，我想到的就是这个解法。原来还认为是枚举，但是仔细看看应该是BFS。因为是记录给自己看的，所以解法不说。
3.直接给结果
这题和之前的黑白子差不多。不过那题我是BFS过的。所以这题，想看看枚举人家怎么做的。但是没想到搜索到了这种解法，对比了一下discuss和他的讲解。下面将代码贴出来。
1
// http://www.cppblog.com/Yusi-Xiao/archive/2010/07/05/77385.html
2// 先看一个简单的问题,如何把'+'变成'-'而不改变其他位置上的状态?
3// 答案是将该位置(i,j)及位置所在的行(i)和列(j)上所有的handle更新一次。
4// 结果该位置被更新了7次,相应行(i)和列(j)的handle被更新了4次,剩下的被更新了2次.
5// 被更新偶数次的handle不会造成最终状态的改变.
6// 因此得出高效解法,在每次输入碰到'+'的时候, 计算所在行和列的需要改变的次数
7// 当输入结束后,遍历数组,所有为奇数的位置则是操作的位置,而奇数位置的个数之和则是最终的操作次数.
8// PS:该题不会有"Impossible"的情况.
9
10#include <stdio.h>
11
12#define Len 4
13
14void main()
15
{
16
int handles[Len][Len] = {0};
17
int i, j, k, step = 0;
18 char c;
19
20 // 核心算法，统计翻转的总次数
21 for (i = 0; i < Len; ++i)
22 {
23 for (j = 0; j < Len; ++j)
24 {
25 scanf("%c\n", &c);
26 if ('+' == c)
27 {
28 handles[i][j]++;
29 for (k = 0; k < Len; ++k)
30 {
31 handles[i][k]++; // 这种算法重复计算i,j 处，但是对于只需要判断奇偶来说无所谓
32 handles[k][j]++;
33
}
34 }
35 }
36 }
37 // 统计奇数的个数
38 for (i = 0; i < Len; ++i)
39 {
40 for (j = 0; j < Len; ++j)
41 {
42 if (handles[i][j] % 2)
43 {
44 step++;
45 }
46 }
47 }
48 printf("%d\n", step);
49
50 // 打印奇数的位置
51 for (i = 0; i < Len; ++i)
52 {
53 for (j = 0; j < Len; ++j)
54 {
55 if (handles[i][j] % 2)
56 {
57 printf("%d %d\n", i + 1, j + 1);
58 }
59 }
60 }
61
}
ps.
1.这个算法居然也用了64ms。
2.一开始用的scanf("%c", &c);忘记了\n,错了。然后居然牛逼的想到scanf("%c\n", &c);哈哈！
3.链接中的作者有部分说错了，在上面的注释我更正了一下。
4.不知道为啥poj的域名变成poj.org....
posted on 2010-10-02 16:52
margin 阅读(548)
评论(0) 编辑 收藏 引用