#P2867. [USACO06NOV] Big Square S

    ID: 3699 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>动态规划 DP2006USACO枚举深度优先搜索 DFS

[USACO06NOV] Big Square S

题目背景

English version

题目描述

农民 John 的牛参加了一次和农民 Bob 的牛的竞赛。

他们在区域中画了一个 N×NN\times N 的正方形点阵,两个农场的牛各自占据了一些点。当然不能有两头牛处于同一个点。

农场的目标是用自己的牛作为 44 个顶点,形成一个面积最大的正方形(不必须和边界平行)。

除了 Bessie 以外,John 其他的牛都已经放到点阵中去了,要确定 Bessie 放在哪个位置,能使得 John 的农场得到一个最大的正方形(Bessie 不是必须参与作为正方形的四个顶点之一)。

输入格式

11 行:一个单独的整数,NN2N1002 \leq N \leq 100)。

2(N+1)2 \sim (N+1) 行:第 i1i-1 行使用 NN 个字符描述区域的第 ii 行。其中,J代表此点被 John 的牛占据,B 代表此点被 Bob 的牛占据,而 * 代表一个未被占据的点。输入保证至少有一个未被占据的点。

输出格式

输出一个整数,表示 John 的农场所能达到的最大面积。如果无法形成正方形,则输出 00

6
J*J***
******
J***J*
******
**B***
******
4