在枚舉分類中已有暴力枚舉的方法解這道題。之后在網(wǎng)上看到大神的高效算法，膜拜之。故copy在此。

/*參考高手的高效解法： > 證明:要使一個(gè)為'+'的符號(hào)變?yōu)?#39;-',必須其相應(yīng)的行和列的操作數(shù)為奇數(shù);可以證明,如果'+'位置對(duì)應(yīng)的行和列上每一個(gè)位置都進(jìn)行一次操作,則整個(gè)圖只有這一'+'位置的符號(hào)改變,其余都不會(huì)改變. > 設(shè)置一個(gè)4*4的整型數(shù)組,初值為零,用于記錄每個(gè)點(diǎn)的操作數(shù),那么在每個(gè)'+'上的行和列的的位置都加1,得到結(jié)果模2(因?yàn)橐粋€(gè)點(diǎn)進(jìn)行偶數(shù)次操作的效果和沒進(jìn)行操作一樣,這就是樓上說的取反的原理),然后計(jì)算整型數(shù)組中一的 > 個(gè)數(shù)即為操作數(shù),一的位置為要操作的位置(其他原來操作數(shù)為偶數(shù)的因?yàn)椴僮鞑⒉话l(fā)生效果,因此不進(jìn)行操作) ********************************* 此上證其可以按以上步驟使數(shù)組中值都為‘-’ ******************************** 在上述證明中將所有的行和列的位置都加1后，在將其模2之前,對(duì)給定的數(shù)組狀態(tài)，將所有的位置操作其所存的操作數(shù)個(gè)次數(shù)，舉例，如果a[i][j]==n,則對(duì)（i,j）操作n次，當(dāng)所有的操作完后，即全為‘-’的數(shù)組。 其實(shí)就是不模2的操作，作了許多的無用功。 以上的操作次序?qū)Y(jié)果無影響，如果存在一個(gè)最小的步驟，則此步驟一定在以上操作之中。（簡(jiǎn)單說下：因?yàn)橐陨喜僮饕呀?jīng)包含了所有可改變欲改變位置的操作了） 而模2后的操作是去掉了所有無用功之后的操作，此操作同樣包含最小步驟。 但模2后的操作去掉任何一個(gè)或幾個(gè)步驟后，都不可能再得到全為‘-’的。（此同樣可證明：因?yàn)椴僮鞔涡驘o影響，先進(jìn)行最小步驟，得到全為‘-’，如果還剩下m步，則在全為‘-’的數(shù)組狀態(tài)下進(jìn)行這m步操作后還得到一個(gè)全為 ‘-’的數(shù)組狀態(tài)，此只能是在同一個(gè)位置進(jìn)行偶數(shù)次操作，與前文模2后矛盾，所以m=0），因此模2后的操作即為最小步驟的操作。 */ #include <iostream> using namespace std;bool mark[4][4]; char s[4][4];int main() {int i,j,k;int ci[16],cj[16];int nas = 0;memset(mark,0,sizeof(mark));for(i = 0;i < 4;i++)cin >> s[i];for(i = 0;i < 4;i++)for(j = 0;j < 4;j++){char c = s[i][j];if(c == '+'){mark[i][j] = !mark[i][j];for(k = 0;k < 4;k++){mark[i][k] = !mark[i][k];mark[k][j] = !mark[k][j];}}}for(i = 0;i < 4;i++)for(j = 0;j < 4;j++)if(mark[i][j] == true){ci[nas] = i + 1;cj[nas] = j + 1;nas ++;}printf("%d\n",nas);for(i = 0;i < nas;i++){printf("%d %d\n",ci[i],cj[i]);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/gj-Acit/archive/2013/03/20/2971538.html

總結(jié)

以上是生活随笔為你收集整理的再谈poj2965（高效算法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。