[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...