dfs并记录最左上角和右下角坐标……

只需判断是否有以下的情况即可O(n^2)

## #. .#

.# #. ## ##

找船个数用floodfill

FloodFill可以深搜...广搜还要判重复...

找到一条船就标记，如果找到的另一条船经过了标记点则判断bad

我的思路

先在外面补半圈"."

仅当有一个2*2的区域中有 3个"#"和1个"."

#. .# ##

.# ## ## #.

才一定是Bad placement. 直接退出

只有当一个"#"的上面和左边都是"." 他才一定是某矩形的左上角

所以只需要边读边判断,两重循环 30行就AC了

程序免

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

极其变态的方法解决的。

是广搜吗?

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 291ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：291ms

FloodFill过了！

感谢楼下的所有大牛。。

只是不会剪枝，搞这么慢！哭。。。

遍历所有的·点，找到一个L拐角就可以PASS掉了

也就是找以下特征的·点：

＃＃　　·＃　　＃·　　＃＃

·＃　　＃＃　　＃＃　　＃·

如果合法就遍历求连通分量个数。

可看样子这样的方法……剪得不好...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 494ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：494ms

题目的意思好象是只要有一个不合法的位置就输出'Bad placement.'

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

rp太好了。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 212ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：212ms

方法不好。。

严重鄙视啊！此题我在自己的机子上蛮好的！数据通过但是交上去以后.......

编译通过...

├ 测试数据 01：运行超时|格式错误...

├ 测试数据 02：运行超时|格式错误...

├ 测试数据 03：运行超时|格式错误...

├ 测试数据 04：运行超时|格式错误...

├ 测试数据 05：运行超时|格式错误...

├ 测试数据 06：运行超时|格式错误...

├ 测试数据 07：运行超时|格式错误...

├ 测试数据 08：运行超时|格式错误...

├ 测试数据 09：运行超时|格式错误...

├ 测试数据 10：运行超时|格式错误...

---|---|---|---|---|---|---|---|-

谁能告诉我为什么啊!!!!!!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

搜长方形：

0.读入.预处理

1.搜其长和宽

2.然后检查在这个长方形里是不是都是‘#’

3.看看长方形周围是不是都是‘.’

4.如果是独立长方形，则inc（t）

5。用淹水法把船给沉没了

6.继续下一个

7.输出t

我最后一个点还是算了　150ms....　floodfill 1000*1000的数组差不多了啊...

如果只有1只船的话.. 好象后面不应该用复数 ships ...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

数据有点弱~~~`

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

如果只有一条的话，是不是要把's'去掉，语法。。。。。。

给大家一种我的判断Bad placement的方法。

方法是这样的：判断船只使用的是floodfill来统记有多少个子结构。但是中间加入了一种统记，每次floodfill的时候记录下当前船只在该纵行有多少个'#',然后判断这只船的纵坐标从最小到最大时'#'是不是一样多,如果一样多。那么很明显这是一个矩形。如果不一样多那么说明这不是矩形。。十分简单，效率很高。可以解决楼上各位列出的特殊情况。为了防止有人cheat暂不贴程序了。