如何解决这个矩阵问题来收集所有种子?

问题描述 投票:1回答:1

问题描述:

[仓鼠哈米(Hammy)找到了一栋装有种子的建筑物。帮助他收集它们。

[建筑物按房间矩阵排列,有些房间里种着种子。进入建筑物后,Hammy只会沿直线一直贯穿建筑物,并收集该直线上的所有种子。该建筑物有许多入口,哈米可以根据需要在任何行或列进入。

他想尽可能少地收集建筑物中的所有种子。

这是建筑物的示例布局:

+---+---+---+---+---+
| * |   | * |   |   |
+---+---+---+---+---+
| * | * |   |   |   |
+---+---+---+---+---+
| * |   |   |   | * |
+---+---+---+---+---+
|   |   |   | * |   |
+---+---+---+---+---+
|   |   |   | * |   |
+---+---+---+---+---+

此建筑物具有25个房间(5X5),但只有8 rooms具有种子(房间中包含'*')。

我们需要找到收集所有种子的最低限度运行。

我的方法:

我试图用一些Greedy Approach解决它,在这里是:

1) Start with row/column that contains maximum rooms of seeds (For example: column 1 for here).

2) Updating rows/columns (no of rooms that contain seeds).

3) Repeating steps 1 & 2 until all the seeds are collected.

因此,对于这个示例,当我应用我的方法时,

[以Column 1开头(包含3个房间),

更新后,下一个将是Column 4

这是现在的建筑物状况,

+--+---+---+--+---+
|  |   | * |  |   |
+--+---+---+--+---+
|  | * |   |  |   |
+--+---+---+--+---+
|  |   |   |  | * |
+--+---+---+--+---+
|  |   |   |  |   |
+--+---+---+--+---+
|  |   |   |  |   |
+--+---+---+--+---+

[现在三个房间包含种子,并且所有种子都位于不同的rowscolumns上,我需要全部拿走,结果我完成了5 runs,即maximum考虑所有种子,所有列始终是一个答案)。无需任何计算,任何人都可以到达这里。运行包含所有行或列。

但是这个问题可以在4次运行中解决。

我正在寻找一种方法/算法来查找最小运行次数(我需要运行哪些行和/或列)。>>

问题描述:仓鼠哈米(Hammy)找到一栋装有种子的建筑物。帮助他收集所有。该建筑按房间矩阵排列,部分房间带有种子。进入建筑物后,哈米(Hammy ...

c++ algorithm matrix greedy
1个回答
0
投票

也许另一种方法是集中精力减少剩余种子的行数/列数。您可以通过像这样计算每一行/列中的种子数来找到行/列。

© www.soinside.com 2019 - 2024. All rights reserved.