[TIOJ] 1097. F.營地

題目連結:http://tioj.infor.org/problems/1097

---

本題就是一個經典的最大0/1子矩陣問題，且限制只能圈正方形，所以就DP吧，dp[i][j]意思是以(i,j)為右下角，最大可以劃出邊長為多少的正方形，而轉移即是看他左上角一格，或上面，或左邊，最小可以畫到多少，然後加一。參考資料
不過本題很陰險的是直接開記憶體會噴掉，所以要滾動或是跟我一樣用個爛爛的做法:開short

#include <bits/stdc++.h>
using namespace std;
#define N 5000

bitset<N + 10> graph[N + 10];
short dp[N + 10][N + 10];

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	while(n+m!=0){
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				int t;
				scanf("%d",&t);
				graph[i][j] = (t==2);
			}
		}
		//1 means ummovable, 0 means movable
		for(int i=0;i<n;i++)if(!graph[i][0])dp[i][0]=1;
		for(int i=0;i<m;i++)if(!graph[0][i])dp[0][i]=1;
		short ans=!graph[0][0];
		for(int i=1;i<n;i++){
			for(int j=1;j<m;j++){
				if(graph[i][j])dp[i][j]=0;
				else dp[i][j] = min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
				ans = max(ans,dp[i][j]);
			}
		}
		printf("%d\n",(int)ans*(int)ans);
		scanf("%d%d",&n,&m);
	}
	return 0;
}