Description

你家剛買了一套新房，想邀請朋友回來慶祝，所以需要一個很大的舉行餐桌，餐桌能容納的人數等于餐桌的周長，你想買一個能容納最多人的餐桌，餐桌的邊必須跟房間的邊平行。
給你的房間的設計，計算最多能邀請的客人數。

Input

第一行包含兩個整數R和C(1<=R,C<=2000)，表示房子的長和寬。
接下來R行每行S個字符（中間沒有空格），“.”表示空白區域，“X”表示有障礙物，餐桌所占區域必須是空白的。

Output

輸出最多能要求的客人數量。

Sample Input

輸入1：
2 2
..
..

輸入2：
4 4
X.XX
X..X
..X.
..XX

輸入3：
3 3
X.X
.X.
X.X

Sample Output

輸出1：
7

輸出2：
9

輸出3：
3

Data Constraint

Hint

【數據規模】
50%的數據R,C<=400
70%的數據R,C<=1000
100%的數據，R,C<=2000
.
.
.
.
.
.
.

分析

搞一個前綴和然后暴力枚舉開始點，然后取最大值
.
.
.
.
.

程序：

#include<iostream> using namespace std; int a[2001][2001],f[2001],ans,n,m,t; char ch; int main() {cin>>n>>m;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){cin>>ch;if (ch=='X') a[i][j]=-1;}for (int i=1;i<=m;i++)if (a[m][i]!=-1) a[m][i]=1;for (int i=n-1;i>=1;i--)for (int k=1;k<=m;k++){if (a[i][k]!=-1)if (a[i+1][k]==-1) a[i][k]=1;else a[i][k]=a[i+1][k]+1;}int min,x;for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (a[i][j]>0){x=j;min=2147483647;while (a[i][x]>0){if (a[i][x]<min) min=a[i][x];if ((x-j+1+min)*2-1>ans) ans=(x-j+1+min)*2-1;x++;}}cout<<ans;return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/9499948.html

總結

以上是生活随笔為你收集整理的餐桌的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。