时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
You are given a M*M cloth with some holes on it. Your task is to find a biggest square cloth from it. The following is an example(M=5)
输入格式
The first line contains the one integer number M (1<= M<=1,000). Then M lines are following. Each line contains M
charactors which “.” means cloth and “H” means hole.
输出格式
The only line of the output contains area of the biggest square cloth mentioned above.
输入样例
5
H...H
.....
.....
.HHH.
.....
输出样例
9
作者
admin
思路：比较经典的模型了，大白上有几乎一样的原题
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = ;
char Map[N][N];
int Up[N][N], Left[N][N], Right[N][N];
int n;
void getL() {
for(int i = ; i <= n; ++i) {
int lo = ;
for(int j = ; j <= n; ++j) {
if(Map[i][j] == '.') {
Up[i][j] = Up[i - ][j] + ;
Left[i][j] = max(Left[i - ][j], lo + );
}else {
Up[i][j] = Left[i][j] = ;
lo = j;
}
}
}
}
int ans = ;
void getR() {
for(int i = ; i <= n; ++i) {
int ro = n + ;
for(int j = n; j >= ; --j) {
if(Map[i][j] == '.') {
Right[i][j] = min(Right[i - ][j], ro - );
}else {
Right[i][j] = n;
ro = j;
}
ans = max(ans, min(Up[i][j], Right[i][j] - Left[i][j] + ));
}
}
}
void show(int a[][N]) {
for(int i = ; i <= n; ++i) {
for(int j = ; j <= n; ++j) printf("%d ", a[i][j]);
puts("");
}
}
int main() {
while(~scanf("%d", &n)) {
for(int i = ; i <= n; ++i) scanf("%s", Map[i] + );
for(int i = ; i <= n; ++i) Up[][i] = ;
for(int i = ; i <= n; ++i) Left[][i] = ;
for(int i = ; i <= n; ++i) Right[][i] = n;
getL();
getR();
printf("%d\n", ans * ans);
}
return ;
}
/*
5
HH.HH
.....
.....
H...H
HHHHH
*/