2012年12月4日 星期二

PKU3251-Big Square

題目: http://poj.org/problem?id=3251
Farmer John擁有很多乳牛,事實上,Farmer Bob也有很多乳牛
他們倆決定來一場世紀乳牛大對決!
現在他們把各自的乳牛放置到一個N*N(100*100)網格的交會點上
希望能圍出一個最大的正方形四個角落都站著自己陣營的乳牛
正方形的邊不一定要和網格平行
(一格只會有0~1隻乳牛,所以只有 空格'*' FJ側'J' 和 FB側'B'三種符號)

現在所有的乳牛都站到網格上了,除了Farmer John的乳牛Bessie之外
把Bessie放進去以後FJ側能圍出多大面積的正方型呢?

(最大的正方形四角不一定要包含Bessie,
給出的測資一定會有至少一個'*'給Bessie站)