塔子哥是一名快递员,他每天都要在城市里送很多快递。他负责的一个小区是一个很特别的地方,这个小区原本是一个军事基地,后来被改造成了住宅区。因为基地的设计很复杂,所以小区的布局也很奇怪,大体上可以看成一个 m×n 个方格组成的矩阵。有些地方还保留了原来的防御设施。这些设施对于普通人来说是不可进入的,所以塔子哥不能穿过它们。(0
代表空地, B
代表楼栋, #
代表防御设施)
小区的住户大多数是退伍军人或者军人家属,他们都有一种特殊的习惯:他们不喜欢下楼取快递,而是要求塔子哥把快递送到他们附近的某个地方,然后他们再去取。这是因为他们觉得下楼太麻烦,而且有些人还有战争创伤,不愿意和外界接触。塔子哥虽然觉得这样很不合理,但是他也不敢得罪这些住户,只能尽量满足他们的要求。
这道题目要求在一个 m × n 的矩阵中,选择最多 k 个派件点,使得派件点能够覆盖尽可能多的楼栋 (B)。派件点的覆盖范围是在同一行或同一列内,距离不超过 s 且不被防御设施 (#) 阻挡的楼栋。快递员只能移动到空地 (0) 或楼栋 (B) 上,不能穿过防御设施
思路步骤 1.确定可达点:
使用广度优先搜索(BFS)从快递员的起始位置 [row, col] 出发,找到所有可以到达的点(0 或 B),这些点是潜在的派件点。
2.标记楼栋位置: