v***n
发帖数: 562 | 1 下面那个is_free方法是什么作用？谢谢！
下面第四版的解答：
Imagine a robot sitting on the upper left hand corner of an NxN
grid. The robot can
only move in two directions: right and down. How many possible paths are
there for
the robot?
FOLLOW UP
Imagine certain squares are “o$ limits”, such that the robot can not
step on them.
Design an algorithm to get all possible paths for the robot.
pg 64
Part 1: (For clarity, we will solve this part assuming an X by Y grid)
Each path has (X-1)+(Y-1) steps. Imagine the following paths:
X X Y Y X (move right -> right -> down -> down -> right)
X Y X Y X (move right -> down -> right -> down -> right)
...
Each path can be fully represented by the moves at which we move right.
That is, if I were to
ask you which path you took, you could simply say “I moved right on step
3 and 4.”
Since you must always move right X-1 times, and you have X-1 + Y-1 total
steps, you have
to pick X-1 times to move right out of X-1+Y-1 choices. Thus, there are
C(X-1, X-1+Y-1) paths
(e.g., X-1+Y-1 choose X-1):
(X-1 + Y-1)! / ((X-1)! * (Y-1)!)
Part 2: Code
We can implement a simple recursive algorithm with backtracking:
1 ArrayList current_path = new ArrayList();
2 public static boolean getPaths(int x, int y) {
3 Point p = new Point(x, y);
4 current_path.add(p);
5 if (0 == x && 0 == y) return true; // current_path
6 boolean success = false;
7 if (x >= 1 && is_free(x - 1, y)) { // Try right
8 success = getPaths(x - 1, y); // Free! Go right
9 }
10 if (!success && y >= 1 && is_free(x, y - 1)) { // Try down
11 success = getPaths(x, y - 1); // Free! Go down
12 }
13 if (!success) {
14 current_path.remove(p); // Wrong way!
15 }
16 return success;
17 } | d****o
发帖数: 1055 | 2 Imagine certain squares are “o$ limits”, such that the robot can not
step on them.
Test This.
upper left hand corner of an NxN
【在 v***n 的大作中提到】
: 下面那个is_free方法是什么作用？谢谢！
: 下面第四版的解答：
: Imagine a robot sitting on the upper left hand corner of an NxN
: grid. The robot can
: only move in two directions: right and down. How many possible paths are
: there for
: the robot?
: FOLLOW UP
: Imagine certain squares are “o$ limits”, such that the robot can not
: step on them.
| v***n
发帖数: 562 | |
|
