hdu 1937 Finding Seats

hdu 1937 Finding Seats"/>

hdu 1937 Finding Seats

其实就是求一个01矩阵中矩阵和为k的矩阵的最小面积。通过将行之间求和，可以通过计算一维数组中的和为k的最短区间来求出当前合并的矩阵中的最小答案。

#include#include#include#include#includeusing namespace std; #define clr(a) memset(a,0,sizeof(a)) int mt[310][310],r,c,k; bool input(){ scanf("%d %d %d",&r,&c,&k); if((r|c|k)==0) return 0; clr(mt); char bf[310]; for(int i=1;i<=r;++i){ scanf("%s",bf+1); for(int j=1;j<=c;++j) mt[i][j]=bf[j]=='.'?1:0; } return 1; }; int fr(int ri){ int ar[310]={0},br[310],ts=INT_MAX; for(int i=ri,h=1;i<=r;++i,++h){ for(int j=1;j<=c;++j) ar[j]+=mt[i][j]; br[0]=0; for(int j=1;j<=c;++j) br[j]=ar[j]+br[j-1]; for(int j=0,l=1;l<=c;++j){ for(;l<=c&&br[l]-br[j]