[LeetCode] 675. Cut Off Trees for Golf Event_Hard tag: BFS
You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:
0
represents theobstacle
can't be reached.1
represents theground
can be walked through.The place with number bigger than 1
represents atree
can be walked through, and this positive number represents the tree's height.
You are asked to cut off all the trees in this forest in the order of tree's height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).
You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can't cut off all the trees, output -1 in that situation.
You are guaranteed that no two trees
have the same height and there is at least one tree needs to be cut off.
Example 1:
Input:
[
[1,2,3],
[0,0,4],
[7,6,5]
]
Output: 6
Example 2:
Input:
[
[1,2,3],
[0,0,0],
[7,6,5]
]
Output: -1
Example 3:
Input:
[
[2,3,4],
[0,0,5],
[8,7,6]
]
Output: 6
Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking.
Hint: size of the given matrix will not exceed 50x50.
这个题其实刚看完觉得有点麻烦啊, 完全就是A star啊, 怎么会只有一个BFS 的tag? 百思不得其解, 然后去看了solution, 确实除了A* 还能够用BFS解, 思路就是先将2D array扫一遍, 然后把元素大于1的值和index放到arr里面, 再sort. 此操作O(m*n* lg(m*n)), 本来我觉得这拉高了时间复杂度, 后来发现, 其实每两个点的最短距离的worst case 是m*n, 所以理论上时间复杂度为 O((m*n)^2), 所以无所谓了. 然后就是把(0,0) 作为source位置, arr里面第一个位置为target 位置, 计算距离d, 同理将arr里面两两计算d, ans = sum(d), 只不过如果有d<0的话, 表明有两个点不通, 那么就直接返回-1.
计算距离d的时候可以用另一个function bfs, 方法跟word ladder里面的其实很像, 找到target 即可.
只是Leetcode好像对python的time很不友好, 这个是time limit exceed, 即使把solution的code 过去也没法被accepted, 反正思路是这样没问题.(应该..)
1. Constraints
1) size of 2D array , not empty, at least one element, max 50 * 50
2) each element >=0
3) return shortest steps
4) return -1 if no solution
5) no duplicates for trees
6) edge case , forest[0][0] == 0, return -1
2. Ideas
BFS T: O((m*n)^2), S: O(m*n)
3. Code
class Solution:
def bfs(self, forest, sr, sc, tr, tc):
queue, visited, dirs = collections.deque([(sr, sc, 0)]), set([(sr, sc)]), [(0,1), (0, -1), (1, 0), (-1, 0)]
while queue:
pr, pc, dis = queue.popleft()
if pr == tr and pc == tc: return dis
for d1, d2 in dirs:
nr, nc = pr + d1, pc + d2
if 0<= nr < lr and 0<= nc < lc and forest[nr][nc] > 0 and (nr,nc) not in visited:
queue.append((nr, nc, dis + 1))
visited.add((nr, nc))
return -1
def cutForest(self, forest):
lr, lc = len(forest), len(forest[0])
if forest[0][0] == 0: return -1 # edge case , 方便bfs不用判断edge
arr = sorted((forest[i][j], i, j) for i in range(lr) for j in range(lc) if forest[i][j] > 1))
sr, sc, ans = 0, 0, 0
for _, tr, tc in arr:
d = self.bfs(forest, sr, sc, tr, tc)
if d < 0: return -1
ans += d
sr, sc = tr, tc
return ans
4. Test cases
1)
[
[1,2,3],
[0,0,0],
[7,6,5]
]
Output: -1 2)
[
[1,3,4],
[2,0,5],
[0,0,6]
]
Output: 6 3)
[
[1,1,6],
[1,0,7],
[2,0,9]
]
Output: 8
最新文章
- React构建单页应用方法与实例
- linux两台服务器之间文件/文件夹拷贝
- python模块httplib的使用
- CSS自适应布局(包括两边宽度固定中间宽度自适应与中间宽度固定两边宽度自适应)
- 有向图的强连通图——Kosaraju
- 在 Linux 中用 nmcli 命令绑定多块网卡
- Android内存管理(2)HUNTING YOUR LEAKS: MEMORY MANAGEMENT IN ANDROID PART 2
- TCP和UDP的区别(转)
- PreparedStatement设置时间
- Nopi Excel导入
- JVM的 GC机制和内存管理
- java 判断手机号码和邮箱的正则表达式
- python 流程控制(条件语句)
- Swift 里字符串(七)stringIndex
- 【LOJ】#2537. 「PKUWC2018」Minimax
- java代码块执行顺序
- css样式整理
- poj2187凸包最远点对
- yii学习笔记(7),数据库操作,联表查询
- 题解 【luogu P2680 NOIp提高组2015 运输计划】