https://vjudge.net/problem/UVA-11464

題意：

給出一個0，1矩陣，現在要求把這個矩陣中的某些0改為1，使得這個矩陣中每個格子的上下左右格子（如果存在）的值之和為偶數，問最少的改變次數，不能達到要求輸出-1。

思路：

其實，只要第一行的狀態定了，接下來所有行的狀態就已經定了，這是經過手算得出的結果。根據一個格子的上左右的值之和，就可以確定它下面的格子的狀態。

那么，只需要枚舉第一行的狀態就可以了，用二進制枚舉的方法。

接下來，判斷這個矩陣是否滿足要求，注意的地方是，如果說原矩陣中為1的在改變后的矩陣中為0，那么這個肯定是不符合要求的，因為只能把0改為1，不能把1改為0。

代碼：

1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 6 int a[20][20]; 7 int b[20][20]; 8 9 int main() 10 { 11 int t; 12 13 scanf("%d",&t); 14 15 int cas =0 ; 16 17 while (t--) 18 { 19 int n; 20 21 scanf("%d",&n); 22 23 for (int i = 0;i < n;i++) 24 for (int j = 0;j < n;j++) 25 scanf("%d",&a[i][j]); 26 27 int k = (1 << n); 28 29 int ans = 1000000; 30 31 for (int i = 0;i < k;i++) 32 { 33 for (int j = 0;j < n;j++) 34 { 35 if ((1 << j) & i) b[0][j] = 1; 36 else b[0][j] = 0; 37 } 38 39 for (int x = 0;x < n - 1;x++) 40 for (int y = 0;y < n;y++) 41 { 42 int sum = 0; 43 44 if (x - 1 >= 0) sum += b[x-1][y]; 45 if (y - 1 >= 0) sum += b[x][y-1]; 46 if (y + 1 < n) sum += b[x][y+1]; 47 48 if (sum & 1) b[x+1][y] = 1; 49 else b[x+1][y] = 0; 50 } 51 52 int tmp = 0; 53 54 bool f = 0; 55 56 for (int x = 0;x < n;x++) 57 for (int y = 0;y < n;y++) 58 { 59 60 if (f) break; 61 62 if (a[x][y] == 0 && b[x][y] == 1) 63 { 64 tmp++; 65 } 66 else if (a[x][y] == 1 && b[x][y] == 0) 67 { 68 f = 1; 69 break; 70 } 71 } 72 73 74 if (f) continue; 75 else ans = min(ans,tmp); 76 } 77 78 if (ans == 1000000) 79 { 80 printf("Case %d: %d\n",++cas,-1); 81 } 82 else printf("Case %d: %d\n",++cas,ans); 83 } 84 85 return 0; 86 }

?

轉載于:https://www.cnblogs.com/kickit/p/7592780.html

總結

以上是生活随笔為你收集整理的uva 11464 Even Parity的全部內容，希望文章能夠幫你解決所遇到的問題。

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