cf D. Broken Monitor

http://codeforces.com/contest/370/problem/D

题意：输入一张图，上面只有两个字符'w'和‘.’ ,如果可以用一个正方形把所有的‘w’围起来，所有的‘w’都在正方形的边上。如果有多种输出最小的一个。

先预处理出[1,1]到[i,j]里面有多少个'w'存在dp[i][j]中。找到正方形的大小，然后枚举找左上角的点。就可以找到符合题意的正方形。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #define maxn 2001
  5 using namespace std;
  6 
  7 char g[maxn][maxn];
  8 int dp[maxn][maxn];
  9 int n,m;
 10 
 11 int get_num(int x1,int y1,int x2,int y2)
 12 {
 13     if(x1>x2||y1>y2) return 0;
 14     return dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];
 15 }
 16 
 17 
 18 int main()
 19 {
 20     while(scanf("%d%d",&n,&m)!=EOF)
 21     {
 22         int max1=0,max2=0,min1=n,min2=m;
 23         int cnt=0;
 24         for(int i=1; i<=n; i++)
 25         {
 26             scanf("%s",g[i]+1);
 27             for(int j=1; j<=m; j++)
 28             {
 29                 if(g[i][j]=='w')
 30                 {
 31                     cnt++;
 32                     min1=min(min1,i);
 33                     min2=min(min2,j);
 34                     max1=max(max1,i);
 35                     max2=max(max2,j);
 36                 }
 37             }
 38         }
 39         bool flag=false;
 40         for(int i=min1+1; i<max1; i++)
 41         {
 42             for(int j=min2+1; j<max2; j++)
 43             {
 44                 if(g[i][j]=='w')
 45                 {
 46                     flag=true;
 47                     break;
 48                 }
 49             }
 50             if(flag) break;
 51         }
 52         if(flag)
 53         {
 54             printf("-1
");
 55         }
 56         else
 57         {
 58             int x1,y1;
 59             bool flag1=false;
 60             int dx=max1-min1+1;
 61             int dy=max2-min2+1;
 62             int size=max(dx,dy);
 63             for(int i=1; i<=n; i++)
 64             {
 65                 for(int j=1; j<=m; j++)
 66                 {
 67                     dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];
 68                     if(g[i][j]=='w')
 69                     {
 70                         dp[i][j]+=1;
 71                     }
 72                 }
 73             }
 74             for(int i=1; i<=n; i++)
 75             {
 76                 if(i+size-1>n)break;
 77                 for(int j=1; j<=m; j++)
 78                 {
 79                     if(j+size-1>m) break;
 80                     if(cnt==get_num(i,j,i+size-1,j+size-1)-get_num(i+1,j+1,i+size-2,j+size-2))
 81                     {
 82                         x1=i;
 83                         y1=j;
 84                         flag1=true;
 85                         break;
 86                     }
 87                 }
 88                 if(flag1) break;
 89             }
 90             if(flag1)
 91             {
 92                 for(int i=x1; i<x1+size; i++)
 93                 {
 94                     for(int j=y1; j<y1+size; j++)
 95                     {
 96                         if((g[i][j]=='.'&&i==x1)||(g[i][j]=='.'&&j==y1)||(g[i][j]=='.'&&i==x1+size-1)||(g[i][j]=='.'&&j==y1+size-1)) g[i][j]='+';
 97                     }
 98                 }
 99                 for(int i=1; i<=n; i++)
100                 {
101                     for(int j=1; j<=m; j++)
102                     {
103                         printf("%c",g[i][j]);
104                     }
105                     printf("
");
106                 }
107             }
108             else
109             {
110                 printf("-1
");
111             }
112         }
113     }
114     return 0;
115 }

View Code