[TIOJ] 1097. F.營地
題目連結:http://tioj.infor.org/problems/1097
本題就是一個經典的最大0/1子矩陣問題,且限制只能圈正方形,所以就DP吧,dp[i][j]意思是以(i,j)為右下角,最大可以劃出邊長為多少的正方形,而轉移即是看他左上角一格,或上面,或左邊,最小可以畫到多少,然後加一。參考資料
不過本題很陰險的是直接開記憶體會噴掉,所以要滾動或是跟我一樣用個爛爛的做法:開short
本題就是一個經典的最大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;
}
留言
張貼留言