HDU 2483 Counting square

Description

There is a matrix of size R rows by C columns. Each element in the matrix is either “0” or “1”. A square is called magic square if it meets the following three conditions. 

(1)  The elements on the four borders are all “1”. 

(2)  Inside the square (excluding the elements on the borders), the number of “1”s and the number of “0”s are different at most by 1. 

(3)  The size of the square is at least 2 by 2. 

Now given the matrix, please tell me how many magic square are there in the matrix. 

Input

The input begins with a line containing an integer T, the number of test cases. 

Each case begins with two integers R, C(1<=R,C<=300), representing the size of the matrix. Then R lines follow. Each contains C integers, either 0 or 1. The integers are separated by a single space. 

Output

For each case, output the number of magic square in a single line.

Sample Input

3

4 4

1 1 1 1

1 0 1 1

1 1 0 1

1 1 1 1

5 5

1 0 1 1 1

1 0 1 0 1

1 1 0 1 1

1 0 0 1 1

1 1 1 1 1

2 2

1 1

1 1

Sample Output

3

2

1

 求符合條件的正方形的數量，由于資料比較大，要用預處理降低複雜度。

#include<iostream>  
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#include<functional>
#include<stack>
using namespace std;
const int maxn = 305;
int n, t, m, sum;
int a[maxn][maxn], f[maxn][maxn] = { 0 }, lx[maxn][maxn][2] = { 0 };

int main(){
  cin >> t;
  while (t--)
  {
    scanf("%d%d", &n, &m);  sum = 0;
    for (int i = 1; i <= n;i++)
      for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
      {
        lx[i][j][0] = lx[i][j - 1][0] + a[i][j];
        lx[i][j][1] = lx[i - 1][j][1] + a[i][j];
      }
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
        f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
        if (a[i][j])
          for (int k = 1; i + k <= n&&j + k <= m; k++)
            if (lx[i][j + k][0] - lx[i][j][0] == k&&lx[i + k][j][1] - lx[i][j][1] == k)
            if (lx[i + k][j + k][0] - lx[i + k][j][0] == k&&lx[i + k][j + k][1] - lx[i][j + k][1] == k)
            {
              int u = f[i + k - 1][j + k - 1] + f[i][j] - f[i][j + k - 1] - f[i + k - 1][j];
              u = (k - 1)*(k - 1) - 2 * u;
              if (u > -2 && u < 2) sum++;
            }
    cout << sum << endl;
  }
  return 0;
}