此提一共有三種解法：
1.枚舉
最樸素的算法，但是一開(kāi)始我居然不知道如何來(lái)枚舉。大概的原理是：以位置1,1開(kāi)始變化。得到16種位置的最小解法，然后選最少的一個(gè)就OK。
2.BFS
一開(kāi)始，我想到的就是這個(gè)解法。原來(lái)還認(rèn)為是枚舉，但是仔細(xì)看看應(yīng)該是BFS。因?yàn)槭怯涗浗o自己看的，所以解法不說(shuō)。
3.直接給結(jié)果
這題和之前的黑白子差不多。不過(guò)那題我是BFS過(guò)的。所以這題，想看看枚舉人家怎么做的。但是沒(méi)想到搜索到了這種解法，對(duì)比了一下discuss和他的講解。下面將代碼貼出來(lái)。
1
// http://www.shnenglu.com/Yusi-Xiao/archive/2010/07/05/77385.html
2// 先看一個(gè)簡(jiǎn)單的問(wèn)題,如何把'+'變成'-'而不改變其他位置上的狀態(tài)?
3// 答案是將該位置(i,j)及位置所在的行(i)和列(j)上所有的handle更新一次。
4// 結(jié)果該位置被更新了7次,相應(yīng)行(i)和列(j)的handle被更新了4次,剩下的被更新了2次.
5// 被更新偶數(shù)次的handle不會(huì)造成最終狀態(tài)的改變.
6// 因此得出高效解法,在每次輸入碰到'+'的時(shí)候, 計(jì)算所在行和列的需要改變的次數(shù)
7// 當(dāng)輸入結(jié)束后,遍歷數(shù)組,所有為奇數(shù)的位置則是操作的位置,而奇數(shù)位置的個(gè)數(shù)之和則是最終的操作次數(shù).
8// PS:該題不會(huì)有"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 // 核心算法，統(tǒng)計(jì)翻轉(zhuǎn)的總次數(shù)
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]++; // 這種算法重復(fù)計(jì)算i,j 處，但是對(duì)于只需要判斷奇偶來(lái)說(shuō)無(wú)所謂
32 handles[k][j]++;
33
}
34 }
35 }
36 }
37 // 統(tǒng)計(jì)奇數(shù)的個(gè)數(shù)
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 // 打印奇數(shù)的位置
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.這個(gè)算法居然也用了64ms。
2.一開(kāi)始用的scanf("%c", &c);忘記了\n,錯(cuò)了。然后居然牛逼的想到scanf("%c\n", &c);哈哈！
3.鏈接中的作者有部分說(shuō)錯(cuò)了，在上面的注釋我更正了一下。
4.不知道為啥poj的域名變成poj.org....
posted on 2010-10-02 16:52
margin 閱讀(570)
評(píng)論(0) 編輯 收藏 引用