正題

題目鏈接：https://vijos.org/p/1197

---

大意

有5*5個開關(guān)，每次選擇一個地方時它和它上下左右的開關(guān)都會取反，求將所有開關(guān)都變成1的最少次數(shù)。

---

解題思路

首先我們知道一個位置一定不會點擊超過一次。這樣我們就可以得出一條性質(zhì)，當(dāng)?shù)谝恍卸家呀?jīng)決定是否點擊過后，第一行就只能由第二行點擊，那么這時第二行只能點擊第一行還沒打開的燈的下面，這樣以此類推的話第二條性質(zhì)就出來了。
如果第一行決定是否點擊的方案了，如果有解的話，那么只有一種點擊方式。
這樣的話我們就可以枚舉第一行每格是否點擊，然后我們就可以推出后面幾行，如果有解的話那么就取最小解。

---

代碼

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int n=5; int s[7],bs[7],ans,mins,t; char a; int main() {scanf("%d",&t);for (int ti=1;ti<=t;ti++){for(int i=1;i<=n;i++){bs[i]=0;for(int j=1;j<=n;j++){cin>>a;a-='0';bs[i]=(bs[i]<<1)+a;//讀入}}mins=2147483647;for (int i=0;i<=31;i++)//枚舉{ans=0;for (int j=1;j<=n;j++)s[j]=bs[j];for (int j=0;j<=n;j++)if (i&(1<<j))//是否點擊{if (j!=n-1)s[1]^=1<<(j+1);s[1]^=1<<j;if (j!=0)s[1]^=1<<(j-1);s[2]^=1<<j;ans++;}//改變和統(tǒng)計for (int j=2;j<=n;j++)for (int k=0;k<n;k++)if (!((s[j-1]>>k)&1))//上一行是否還有{if (k!=n-1)s[j]^=1<<(k+1);s[j]^=1<<k;if (k!=0)s[j]^=1<<(k-1);s[j+1]^=1<<k;ans++;}//改變和統(tǒng)計if (s[n]==31)//有解mins=min(mins,ans);//取最小答案}if (mins>6) printf("-1\n");else printf("%d\n",mins);} }

總結(jié)

以上是生活随笔為你收集整理的vijos1197-费解的开关【递推,枚举,位运算】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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