问题描述:
[仓鼠哈米(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
,
这是现在的建筑物状况,
+--+---+---+--+---+
| | | * | | |
+--+---+---+--+---+
| | * | | | |
+--+---+---+--+---+
| | | | | * |
+--+---+---+--+---+
| | | | | |
+--+---+---+--+---+
| | | | | |
+--+---+---+--+---+
[现在三个房间包含种子,并且所有种子都位于不同的rows
或columns
上,我需要全部拿走,结果我完成了5 runs
,即maximum
(考虑所有种子,所有列始终是一个答案)。无需任何计算,任何人都可以到达这里。运行包含所有行或列。
但是这个问题可以在4次运行中解决。
我正在寻找一种方法/算法来查找最小运行次数(我需要运行哪些行和/或列)。>>
问题描述:仓鼠哈米(Hammy)找到一栋装有种子的建筑物。帮助他收集所有。该建筑按房间矩阵排列,部分房间带有种子。进入建筑物后,哈米(Hammy ...
也许另一种方法是集中精力减少剩余种子的行数/列数。您可以通过像这样计算每一行/列中的种子数来找到行/列。