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:

  1. 0 represents the obstacle can't be reached.
  2. 1 represents the ground can be walked through.
  3. The place with number bigger than 1 represents a tree 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

最新文章

  1. Java内存区域与内存溢出异常
  2. Java Garbage Collection基础详解------Java 垃圾回收机制技术详解
  3. H264与RTP
  4. 【Remoting】.Net remoting方法实现简单的在线升级(上篇:更新文件)
  5. 【poj2774】 Long Long Message
  6. Redis 数据库
  7. Android Non-UI to UI Thread Communications(Part 1 of 5)
  8. zoj 3690 Choosing number
  9. Adding Swap Files
  10. Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined)
  11. icheck样式绑定与翻页保持
  12. SmartCoder每日站立会议02
  13. 别人的Linux私房菜(19)认识与分析日志文件
  14. 14.statefulset服务
  15. FFmpeg简易播放器的实现-最简版
  16. (转)Mybatis insert后返回主键给实体对象(Mysql数据库)
  17. php flock 文件锁
  18. 记一次spring-session登录后失效的问题
  19. Delphi XE7编译安卓程序出错了
  20. GSAP 官方文档(结贴)

热门文章

  1. 【ORACLE 】 ORA-00031 标记要删去的会话(解决)
  2. eclipse中改变默认的workspace的方法
  3. 使用MSBUILD 构建时出错 error MSB3086: 任务未能使用 SdkToolsPath“”或注册表项“XXX”找到“LC.exe”,请确保已设置 SdkToolsPath。
  4. Rope整理(可持久化神器)
  5. 【黑金原创教程】【FPGA那些事儿-驱动篇I 】实验八:PS/2模块② — 键盘与组合键
  6. 23种设计模式之观察者模式(Observer)
  7. &#39;cmd&#39; 不是内部或外部命令,也不是可运行的程序 或批处理文件.
  8. Yii---使用事物
  9. Django---简单模板遍历渲染
  10. mini2440:通过JLink烧写BootLoader到Nor Flash