- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在为编程比赛做准备,我想知道如何解决这个问题。我猜这是几何问题,而且我似乎对解决它没有任何想法。
这里是:
有一个院子,院子里有狼和羊。院子里也有不允许通过的障碍物。狼用“w”表示,羊用“s”表示,方 block 用“#”表示,每个人都可以移动的空间是“.”。 .所以可能的输入看起来像:
8 8
.######.
#..s...#
#.####.#
#.#w.#.#
#.#.s#s#
#s.##..#
#.w..w.#
.######.
院子上方的 2 个数字是行 x 列。
如您所见,院子里可以形成不同种类的扇区。这里有两个部门:
####
#.w#
####
#s.#
第一个是狼,第二个是羊。因为它们被放置在两个不同的扇区(即狼无法接近羊),所以他不能吃羊。如果他们在同一个扇区,狼就会吃羊。
我想问你的问题是:给定一个像上面那样的输入,我应该如何计算有多少羊会存活下来?我如何在 C++ 中表示“院子”?算法应该是什么样的?有没有了解类似问题和问题的资料?
感谢任何帮助。先感谢您。
最佳答案
这个问题基本上就是找connected sub-graphs (aka components)的问题对于给定的图形。
您可以通过将每个“非 block ”坐标表示为图形节点来解决该问题,并链接图形中的 2 个相邻坐标。然后使用 BFS(或适合该主题的任何其他算法 - 我确信任何网页或 Wiki 在图算法上都会有一个关于它的各种算法列表。
一旦你有了你的子图,只需找到哪些子图有零只狼(通过找到每个狼坐标在哪个子图上),然后数这些子图中的羊。
希望这足以让您开始。
关于c++ - 帮助解决几何问题 - 不知道,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2255164/
这个问题在这里已经有了答案: How to get all enum values in Java? (8 个回答) 关闭5年前。 我想创建一个 JComboBox 来处理选择给它的任何 Enum。为
我是一名优秀的程序员,十分优秀!