動的系計画法 その２

【問題】
一辺が1メートルのマス目上に区切られた全体 hメートル * wメートルの土地がある。
木や岩といった障害物のあるマス目には家を建てられない。ここで、障害物を避けて建てられる最大の正方形の平屋の面積を求めなさい。

入力
最初の行に整数hと整数w、続いて以下のようにh行の土地の情報（障害物がある場合に Mij=1、なければ Mij=0）
M11 M12 ... M1w
M21 M22 ... M2w
:
Mh1 Mh2 ... Mhw

出力
面積の最大値を出力して改行して終了

制約
1 ≦ h, w ≦ 1,400

入力例

4 5
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
0 0 0 1 0

出力例

9

【解法】
T[i][j]: (i, j)の左上に作ることのできる最大の正方形の編の長さ。

if((i, j)のマス== 0){
T[k][i] = min(T[k-1][i], T[k][i-1], T[k-1][i-1])+1;　//左、上、斜め左上の一番小さい値に１をたす。
}else{
T[k][i] = 0; //　１の場合には0
}

【コード】

#include <stdio.h>

int min(int a, int b, int c){
    int ans;
    if(a > b){
        ans = b;
    }else{
        ans = a;
    }
    if(c < ans){
        ans = c;
    }
    return ans;
}

void countSquare(int n, int m, int data[1000][1000]){
  int ans=0, i, j,k,x,y, flag_one=0,tmp,T[1000][1000],g;
  
  for(i=0;i<m;i++){
      if(data[0][i]==1){
          T[0][i] = 0;    
      }else{
          T[0][i] = 1;
      }
      
  }
  for(i=0;i<n;i++){
      if(data[i][0]==0){
          T[i][0] = 1;
      }else{
          T[i][0] = 0;
      }
  }
  
  for(k=1;k<min(n,m, 1000);k++){
    for(i=k;i<n;i++){
        if(data[i][k] == 0){
            T[i][k] = min(T[i-1][k], T[i][k-1], T[i-1][k-1])+1;
        }else{
            T[i][k] = 0;
        }
        
    }
    for(i=k;i<m;i++){
        if(data[k][i] == 0){
            T[k][i] = min(T[k-1][i], T[k][i-1], T[k-1][i-1])+1;
        }else{
            T[k][i] = 0;
        }
    }
  }
  
  for(i=0;i<n;i++){
      for(j=0;j<m;j++){
          if(ans < T[i][j]){
              ans = T[i][j];
          }
      }
  }
  
  printf("%d\n",ans*ans);
  return;
}

int main(void){
  int m,n,data[1000][1000],i,j;
  scanf("%d %d",&n, &m);

  for(i=0;i<n;i++){
    for(j=0;j<m;j++){
      scanf("%d",&data[i][j]);
    }
  }
  countSquare(n,m,data);
  return 0;
}