此提一共有三種解法：
1.枚舉
最樸素的算法，但是一開始我居然不知道如何來枚舉。大概的原理是：以位置1,1開始變化。得到16種位置的最小解法，然后選最少的一個就OK。
2.BFS
一開始，我想到的就是這個解法。原來還認為是枚舉，但是仔細看看應該是BFS。因為是記錄給自己看的，所以解法不說。
3.直接給結果
這題和之前的黑白子差不多。不過那題我是BFS過的。所以這題，想看看枚舉人家怎么做的。但是沒想到搜索到了這種解法，對比了一下discuss和他的講解。下面將代碼貼出來。
1
// http://m.shnenglu.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 閱讀(557)
評論(0) 編輯 收藏 引用