題意：有1塊n*m大的草坪，’.’表示空地，’x’表示種了棵樹，現(xiàn)在要給這塊草坪建1個(gè)矩形柵欄，柵欄必須建在空地上，問柵欄建好的最大周長是多少，也就是最多占用了多少個(gè)空地。
題解：暴力，需要預(yù)處理出每一個(gè)空地右側(cè)空地的數(shù)量存到r[i][j]和下方空地的數(shù)量d[i][j]，然后枚舉每一個(gè)空地把它當(dāng)作柵欄的左上角頂點(diǎn)，根據(jù)r和d兩個(gè)數(shù)組得到上和左兩條邊可能的長度，然后枚舉上和左的長度如果下和右也都滿足條件(即不出現(xiàn)’x’)，更新最大值。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 505;
int n, m;
char g[N][N], r[N][N], d[N][N];
int main() {
while (scanf("%d%d", &n, &m) == 2) {
memset(r, 0, sizeof(r));
memset(d, 0, sizeof(d));
for (int i = 0; i < n; i++)
scanf("%s", g[i]);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (g[i][j] == '.') {
for (int k = j + 1; k < m && g[i][k] != 'x'; k++)
r[i][j]++;
for (int k = i + 1; k < n && g[k][j] != 'x'; k++)
d[i][j]++;
}
}
int res = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (g[i][j] == '.') {
for (int r1 = r[i][j]; r1 >= 1; r1--)
for (int d1 = d[i][j]; d1 >= 1; d1--)
if (r[i + d1][j] >= r1 && d[i][j + r1] >= d1)
res = max(res, 2 * (r1 + d1));
}
}
if (res >= 4)
printf("%d
", res);
else
printf("impossible
");
}
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
