主题链接：

意甲冠军：特定n*m矩阵

X代表色 .代表无色

随着x*y形刷子去涂色。

刷子每次能够→或↓移动随意步。

若可以染出给定的矩阵，则输出最小的刷子的面积

若不能输出-1

思路：

先找到连续最小的x,y

由于至少一个边界和x或y相等，所以枚举(x,i) 和 (i,y)就能够了。

#pragma comment(linker, "/STACK:102400000,102400000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define N 1010int top;char s[N][N];int n, m, stx, sty;int H(int h, int l, int r){//扫一行 -1表示全是. 1表示全是X 0表示都有    if(h>n || r>m) return -2;    int cnt = 0;    for(int i = l; i <= r; i++)        if(s[h][i]=='X')cnt++;    if(cnt==0)return -1;    if(cnt==r-l+1)return 1;    return 0;}int L(int l, int S, int X){    if(l>m || X>n) return -2;    int cnt = 0;    for(int i = S; i <= X; i++)        if(s[i][l]=='X')cnt++;    if(cnt==0)return -1;    if(cnt==X-S+1)return 1;    return 0;}bool ok(int x, int y){  //  printf(" ++++++(%d,%d)\n", x,y);    int nowx = stx, nowy = sty;    if(nowx + x-1 > n || nowy + y-1>m)return false;    for(int i = 0; i < x; i++)        for(int j = 0; j < y; j++)            if(s[i+nowx][j+nowy]!='X')return false; //   puts("---");put(); puts("-----");    int cnt = x*y;    while(1){        if(nowx + x <= n && s[nowx+x][nowy] =='X')        {            nowx ++;            for(int i = 0; i < y; i++)                if(s[nowx+x-1][i+nowy]!='X')                return false;            cnt += y;        }        else if(nowy + y <= m && s[nowx][nowy+y] == 'X')        {            nowy++;            for(int i = 0; i < x; i++)                if(s[i+nowx][nowy+y-1]!='X')                return false;            cnt += x;        }        else break;    //    puts("******");put();    }    return cnt == top;}int hehe; int feifei;int x, y;void find_xy(){    x = N, y = N;    for(int i = 1; i <= m; i++) {        int cnt = 0;        for(int j = 1; j <= n; j++)        {            if(s[j][i]=='.')            {                if(cnt) x = min(x, cnt);                cnt = 0;            }            else                cnt++;        }        if(cnt) x = min(x, cnt);    }    for(int i = 1; i <= n; i++) {        int cnt = 0;        for(int j = 1; j <= m; j++)        {            if(s[i][j]=='.')            {                if(cnt) y = min(y, cnt);                cnt = 0;            }            else cnt++;        }        if(cnt) y = min(y, cnt);    }}int solve(){    int ans = N*N;    for(int i = 1; i <= x; i++)        if(ok(i,y)) {            ans = i*y;            break;        }    for(int i = 1; i <= y && x*i
          
            n*m) return -1; return ans;}void input(){ stx = -1; top = 0; for(int i = 1; i <= n; i++) { scanf("%s", s[i]+1); for(int j = 1; j <= m; j++) { if(stx==-1 && s[i][j]=='X'){ stx = i, sty = j; } top += s[i][j]=='X'; } }}int main(){ while(cin>>n>>m){ input(); find_xy(); printf("%d\n", solve()); } return 0;}
          
         
        
       
      
     

版权声明：本文博主原创文章，博客，未经同意不得转载。