[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology