UVA 322 ships (POJ 1138)

最新推荐文章于 2020-12-21 18:04:45 发布

hackerwin7

最新推荐文章于 2020-12-21 18:04:45 发布

阅读量1.5w

点赞数

分类专栏： ACM_图论 ACM_DFS ACM_模拟 ACM_剪枝文章标签： uva ships 算法数据结构 DFS

本文链接：https://blog.csdn.net/hackerwin7/article/details/40182021

版权

这道题目是关于经典的猜船游戏，要求判断在已知部分信息的情况下，是否能通过最多一次错误找到所有船只的位置。输入包含多个游戏情况，每个情况给出一个矩形网格表示当前的船只状态。你需要决定是否能确定所有船只位置，最多允许一次误击。解决方案包括使用深度优先搜索（DFS）来尝试所有可能的船只布局，并分析是否存在唯一解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目地址：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=258

http://poj.org/problem?id=1138

题目描述：

Ships

Probably everyone who ever attended school knows the game where two opposing players place a set of ships on a sheet of paper and try to eliminate each other's ships by guessing their location.

In our version of the game, your opponent has distributed the following seven ship patterns over a rectangular grid of squares:

                      xx   xx     xx   x       x    x
                      xx    xx   xx    xxx   xxx   xxx   xxxx

Each ship pattern covers exactly four squares. The patterns may be rotated but not mirrored. All patterns are guaranteed to be placed completely within the boundaries of the rectangle and not to overlap each other, whereas touching another pattern or the border is allowed.

We assume that we are in the middle of the game and that several squares have already been uncovered. You will be given a rectangular grid of squares representing your current knowledge about the positions of your enemy's ships. Every square is marked by one of the following characters:

`x' if a ship covers the square
`o' if no ship covers the square
`.' if the square has not yet been uncovered

Given that information, you are to decide whether you can determine all remaining `x' squares with at most one miss, i.e. whether you could uncover the `.' squares without getting more than one `o' square before you had all `x' squares uncovered. This means you are allowed to hit a `o' if then the solution becomes unique.

Input

The input file contains several game situations. Every test case starts with a line containing two integers w and h. These define width and height of the game rectangle, where .

Each of the next h lines contains a string of w characters. Each of these characters is either `x', `o' or `.', depending on the state of the corresponding square.

A blank line separates each game from the next. The input file ends with a game having w = 0 and h = 0. This game should not be processed.

Output

For each test case you should first output a line containing the number of the game, followed by a line containing either `yes.' (if you can determine all `x' with at most one miss) or `no.' (if you cannot deter

最低0.47元/天解锁文章