地址：http://acm.hdu.edu.cn/showproblem.php?pid=2483

題意：給一個n*m的0-1矩陣。在里面找符合條件的方陣。條件有3個：1.方陣的4條邊上全為1；2.方陣內（除了4條邊的）0和1的個數之差不超過1；3.方陣大小至少為2*2。問能找到幾個這樣的方針。

mark：最樸素的做法是枚舉所有的1當做要找的方陣左上角的元素。然后判斷四邊是否全為1，再統計內部0和1的個數。但是每次判斷邊上的1和計算內部1的數量復雜度太高，肯定是不行的。

我們用一個數組sum[i][j]表示從矩形左上角到(i,j)這個位置里1的個數。在計算區域內1的個數的時候可以利用這個sum[i][j]數組得到。sum[i][j]需要預處理出來：sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+g[i][j]。

我們用一個數組row[i][j]表示第i行中第j個元素是“連續的第幾個1”。例如111011對應的row[i]就是123012。判斷橫邊是否是連續的1的時候，可以用row[i][right]-row[i][left-1]的結果和right-left比較，相同則全為1。row數組需要預處理出來：row[i][j] = (g[i][j]?row[i][j-1]+1:0);

豎邊也是這樣預處理出來。

這樣判斷一個給定的方陣是否符合要求，只需要利用上面3個輔助數組，O(1)地完成，復雜可以符合要求了。

?

代碼：

1 # include <stdio.h> 2 # include <string.h> 3 4 5 int g[310][310] ; 6 int sum[310][310] ; 7 int row[310][310], col[310][310] ; 8 int n, m ; 9 10 11 int abs(int x){return x<0?-x:x;} 12 13 14 int check(int x, int y, int xx, int yy) 15 { 16 int _1 = sum[xx-1][yy-1]-sum[xx-1][y]-sum[x][yy-1]+sum[x][y] ; 17 int _0 = (xx-x-1)*(yy-y-1) - _1 ; 18 if (abs( _1 - _0) > 1) return 0 ; 19 if (row[x][yy] - row[x][y] != yy-y) return 0 ; 20 if (row[xx][yy]-row[xx][y] != yy-y) return 0 ; 21 if (col[xx][y] - col[x][y] != xx-x) return 0 ; 22 if (col[xx][yy] - col[x][yy] != xx-x) return 0 ; 23 return 1 ; 24 } 25 26 27 int main () 28 { 29 int T ; 30 int i, j, k ; 31 int l, t, r, d, ans ; 32 int flag ; 33 34 scanf ("%d", &T) ; 35 while (T--) 36 { 37 scanf ("%d%d", &n, &m) ; 38 for (i = 1 ; i <= n ; i++) 39 for (j = 1 ; j <= m ; j++) 40 scanf ("%d", &g[i][j]), 41 sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+g[i][j], 42 row[i][j] = ((g[i][j])?(row[i][j-1]+1):0), 43 col[i][j] = ((g[i][j])?(col[i-1][j]+1):0) ; 44 ans = 0 ; 45 for (i = 1 ; i <= n ; i++) 46 for (j = 1 ; j <= m ; j++) if (g[i][j]) 47 for (k = 1 ; i+k<=n && j+k<=m ; k++) 48 if (check(i,j,i+k,j+k)) ans++ ; 49 printf ("%d\n", ans) ; 50 } 51 return 0 ; 52 }

?

轉載于:https://www.cnblogs.com/lzsz1212/archive/2013/05/17/3083768.html

總結

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

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