c++ - 帮助解决几何问题 - 不知道

Question

我正在为编程比赛做准备，我想知道如何解决这个问题。我猜这是几何问题，而且我似乎对解决它没有任何想法。

这里是:

有一个院子，院子里有狼和羊。院子里也有不允许通过的障碍物。狼用“w”表示，羊用“s”表示，方 block 用“#”表示，每个人都可以移动的空间是“.”。 .所以可能的输入看起来像:

8 8
.######.
#..s...#
#.####.#
#.#w.#.#
#.#.s#s#
#s.##..#
#.w..w.#
.######.

院子上方的 2 个数字是行 x 列。

如您所见，院子里可以形成不同种类的扇区。这里有两个部门:

####
#.w#
####
#s.#

第一个是狼，第二个是羊。因为它们被放置在两个不同的扇区(即狼无法接近羊)，所以他不能吃羊。如果他们在同一个扇区，狼就会吃羊。

我想问你的问题是:给定一个像上面那样的输入，我应该如何计算有多少羊会存活下来？我如何在 C++ 中表示“院子”？算法应该是什么样的？有没有了解类似问题和问题的资料？

感谢任何帮助。先感谢您。

Answer 1

这个问题基本上就是找connected sub-graphs (aka components)的问题对于给定的图形。

您可以通过将每个“非 block ”坐标表示为图形节点来解决该问题，并链接图形中的 2 个相邻坐标。然后使用 BFS(或适合该主题的任何其他算法 - 我确信任何网页或 Wiki 在图算法上都会有一个关于它的各种算法列表。

一旦你有了你的子图，只需找到哪些子图有零只狼(通过找到每个狼坐标在哪个子图上)，然后数这些子图中的羊。

希望这足以让您开始。