費解的開關

joyoi-tyvj 1266

題目大意：

有5*5的一個圖，每個點的數值是1或0，如果將一個點的數值取反，那這個點上下左右的點都會取反，現在問你將所有點都變為1最少要多少步，如果步數大于6或無法全變成1的話就輸出-1（有n組數據）

輸入樣例

3 00111 01011 10001 11010 1110011101 11101 11110 11111 1111101111 11111 11111 11111 11111

輸出樣例

3 2 -1

解題思路：

首先我們可以發現一個點取反兩次和沒取反是一樣的，所以我們可以暴力枚舉25個點變不變，但這樣就要$o(2^{25}25n)$，就絕對會炸
然后我們一行一行地來看，可以發現如果當前行處理后，當前行0的位置下方必須點，1的位置下方不能點，然后我們就可以只枚舉第一行然后剩下的直接算出來，最后直接判斷最后一行合不合法即可，時間復雜度$o(2^{5}25n)$

代碼：

#include<cstdio> #define min(a,b) (a)<(b)?(a):(b) using namespace std; int n,ans,a[7][7],b[7][7]; int js() {int sum=0;for (int i=1;i<=5;++i)for (int j=1;j<=5;++j)b[i][j]=a[i][j];//用b來臨時計算for (int i=1;i<=4;++i)for (int j=1;j<=5;++j)if (!b[i][j])//如果是0就下方的數取反{b[i][j]^=1;b[i+1][j]^=1;b[i+2][j]^=1;b[i+1][j-1]^=1;b[i+1][j+1]^=1;sum++;}for (int i=1;i<=5;++i)if (!b[5][i])//不合法return 10;//超過6就可以了return sum; } void dfs(int dep,int x) {if (dep>5){ans=min(ans,x+js());//求最小值return;}a[1][dep]^=1;//取反a[1][dep-1]^=1;a[1][dep+1]^=1;a[2][dep]^=1;dfs(dep+1,x+1);a[1][dep]^=1;//不取反a[1][dep-1]^=1;a[1][dep+1]^=1;a[2][dep]^=1;dfs(dep+1,x);return; } int main() {scanf("%d",&n);for (int t=1;t<=n;++t){for (int i=1;i<=5;++i)for (int j=1;j<=5;++j)scanf("%1d",&a[i][j]);//輸入一位數ans=10;dfs(1,0);printf("%d\n",ans<7?ans:(-1));}return 0; }

總結

以上是生活随笔為你收集整理的【结论】【dfs】费解的开关（joyoi-tyvj 1266）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。