题目
土豪聪要请客(stol)
众所周知，聪哥(ndsf)是个土豪，不过你们不知道的是他的MZ和他的RMB一样滴多,某天土豪聪又赚了10^10000e的RMB，他比较开心，于是准备请客。他在自己在XX星上的别墅里面大摆酒席，想要邀请尽可能多的MZ来参加他的宴会。他将会同MZ一起坐在一个巨大的长方形桌子上。这个桌子能坐下的人数等于他的边长。聪哥要求他的桌子能够放进他的别墅，并且桌子的边必须与别墅的边界平行。给定别墅的平面图，请你求出聪哥最多可以请多少个MZ。
输入格式
第一行n,m。表示别墅的长宽
下面n行，每行M个字符，表示一个方块是空的(‘ ’)或是被占用了(‘X’)。
聪哥只要他的桌子放在别墅里，并且桌子不能占用任何一个已经占用了的方块。
输出格式
一个数，表示聪哥最多可以请几个Maze。
样例输入1
2 2
..
..
样例输出1
7
样例输入2
4 4
X.XX
X..X
..X.
..XX
样例输出2
9
最大01子矩阵问题， 给出一个只包含0和1的矩阵，求出其中只包含1的最大的矩阵。
如下矩阵中：
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
最大全1子矩阵为 【2 * 2】
求解最大子矩阵
①：对于非零数字 G[i][j]， 设 F[i][j] 表示第i行 G[i][j] 前面连续1的个数 +1(+1 表示 G[i][j] 本身) 比如对于 0 1 1 0 1 1 1 ，F数组为 0 1 2 0 1 2 3
②：对于非零数字 G[i][j]， 在第j列上 向上向下 扫描，遇到比 F[i][j] 小的则停止， 至此就得到了该矩阵的 长和宽。
代码
/*
* Copyright © Eliot
* Date: 2016-10-24
* Author: Eliot
* Description: 求最大01子矩阵
* QQ: 1161142536
*/
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
#define MAX 401
int n = 0, m = 0;
int G[MAX][MAX] = { 0 };
int F[MAX][MAX] = { 0 };
string str;
int ans = 0;
int main() {
//读入矩阵
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++) {
cin >> str;
for (int j = 0; j < str.length(); j ++) {
char ch = str[j];
switch(ch) {
case '.':
G[i][j + 1] = 1;
break;
case 'X':
G[i][j + 1] = 0;
break;
}
}
}
//计算 连续1
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (G[i][j] == 1) F[i][j] = 1;
if (G[i][j] == G[i][j - 1]) F[i][j] += F[i][j - 1];
}
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (G[i][j] == 1) {
//向上查找
int nNow = F[i][j], nI = i;
int up = 0, down = 0;
while (true) {
if (F[nI][j] < nNow || nI < 0) break;
up ++;
nI --;
}
nI = i;
//向下查找
while (true) {
if (F[nI][j] < nNow || nI > n) break;
down ++;
nI ++;
}
ans = max(ans, (up + down - 1 + F[i][j]) * 2);
}
}
}
cout << ans - 1 << endl;
return 0;
}