主题链接：点击打开链接
意甲冠军：特定n*m矩阵
X代表色 .代表无色
随着x*y形刷子去涂色。
刷子每次能够→或↓移动随意步。
若可以染出给定的矩阵，则输出最小的刷子的面积
若不能输出-1
思路：
先找到连续最小的x,y
由于至少一个边界和x或y相等，所以枚举(x,i) 和 (i,y)就能够了。
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
#define N 1010
int 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<ans; i++)
if(ok(x,i))
{
ans = x*i;
break;
}
if(ans > 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;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。