Cracking Coding Interview - 8.2 Robot in a Grid

2019-08-23 1 分钟阅读 ARTS-A

Robot in a Grid: Imagine a robot sitting on the upper left corner of grid with r rows and c columns.The robot can only move in two directions, right and down, but certain cells are “off limits” such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.

Hints: #331, #360, #388

解法1

机器人从(1, 1)开始：

  1. 右移，在剩下的(2, 1)~(r, c)网格里找路线
  2. 下移，在剩下的(1, 2)~(r, c)网格里找路线

然后以此类推。

Base Condition：

  • 当x == r时只能右移
  • 当c == 1时只能下移
  • 当遇到坏掉的cell的时候停止探索，报告失败
  • 当遇到右下角的时候停止探索，报告成功

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public String findPath(int row, int col) {
  StringBulder path = new StringBuilder();
  boolean success = findPathInternal(1, 1, col, row, path);
  if (success) {
    return path.toString();    
  }
  return null;
}

public boolean findPathInternel(int x1, int y1, int x2, int y2, StringBuilder path) {
  if (isOffLimit(x1, y1)) {
    // 某个cell坏掉了
    return false;
  }
  if (x1 == x2 && y1 == y2) {
    return true;
  }
  int end = path.length();
  boolean success = false;
  if (x1 < x2) {
    path.add('R');
    success |= findPathInternal(x1 + 1, y1, x2, y2, path);
  }
  if (!success) {
    path.delete(end, path.length());
  }
  
  if (y1 < y2) {
    path.add('D');
    success |= findPathInternal(x1, y1 + 1, x2, y2, path);
  }
  if (!success) {
    path.delete(end, path.length());
  }
  return success;
}
Cracking Coding Interview - 8.1 Triple Step
Cracking Coding Interview - 8.3 Magic Index

版权

CC BY-NC-ND 4.0

相关文章

评论