Cracking the coding interview--Q8.2

January 9, 2013
作者:Hawstein
出处:http://hawstein.com/posts/8.2.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

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 “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

译文:

在一个N*N矩阵的左上角坐着一个机器人,它只能向右运动或向下运动。那么, 机器人运动到右下角一共有多少种可能的路径?

进一步地,

如果对于其中的一些格子,机器人是不能踏上去的。设计一种算法来获得所有可能的路径。

解答

为了一般化这个问题,我们假设这个矩阵是m*n的,左上角的格子是(1, 1), 右下角的坐标是(m, n)。

解法一

这个题目可以递归来解,如何递归呢?首先,我们需要一个递推公式, 对于矩阵中的格子(i, j),假设从(1, 1)到它的路径数量为path(i, j), 那么,有:

path(i, j) = path(i-1, j) + path(i, j-1)

很好理解,因为机器人只能向右或向下运动,因此它只能是从(i-1, j)或(i, j-1) 运动到(i, j)的,所以路径数量也就是到达这两个格子的路径数量之和。然后, 我们需要一个初始条件,也就是递归终止条件,是什么呢?可以发现, 当机器人在第一行时,不论它在第一行哪个位置,从(1, 1)到达那个位置都只有一条路径, 那就是一路向右;同理,当机器人在第一列时,也只有一条路径到达它所在位置。 有了初始条件和递推公式,我们就可以写代码了,如下:

ll path(ll m, ll n){
    if(m == 1 || n == 1) return 1;
    else return path(m-1, n) + path(m, n-1);
}

ll是数据类型long long。

解法二

如果用纯数学的方法来解这道题目,大概也就是个高中排列组合简单题吧。 机器人从(1, 1)走到(m, n)一定要向下走m-1次,向右走n-1次,不管这过程中是怎么走的。 因此,一共可能的路径数量就是从总的步数(m-1+n-1)里取出(m-1)步,作为向下走的步子, 剩余的(n-1)步作为向右走的步子。

C(m-1+n-1, m-1)=(m-1+n-1)! / ( (m-1)! * (n-1)! )

代码如下:

ll fact(ll n){
    if(n == 0) return 1;
    else return n*fact(n-1);
}
ll path1(ll m, ll n){
    return fact(m-1+n-1)/(fact(m-1)*fact(n-1));
}

对于第二问,如果有一些格子,机器人是不能踏上去的(比如说放了地雷XD), 那么,我们如何输出它所有可能的路径呢?

让我们先来考虑简单一点的问题,如果我们只要输出它其中一条可行的路径即可, 那么我们可以从终点(m, n)开始回溯,遇到可走的格子就入栈, 如果没有格子能到达当前格子,当前格子则出栈。最后到达(1, 1)时, 栈中正好保存了一条可行路径。代码如下:

bool get_path(int m, int n){
    point p; p.x=n; p.y=m;
    sp.push(p);
    if(n==1 && m==1) return true;
    bool suc = false;
    if(m>1 && g[m-1][n])
        suc = get_path(m-1, n);
    if(!suc && n>1 && g[m][n-1])
        suc = get_path(m, n-1);
    if(!suc) sp.pop();
    return suc;
}

其中二维数组g表示的是M*N的矩阵,元素为1表示该位置可以走,为0表示该位置不可走。 这个只能得到其中一条可行路径,但题目是要求我们找到所有可行路径,并输出。 这样的话,又该怎么办呢?我们从(1, 1)开始,如果某个格子可以走, 我们就将它保存到路径数组中;如果不能走,则回溯到上一个格子, 继续选择向右或者向下走。当机器人走到右下角的格子(M, N)时,即可输出一条路径。 然后程序会退出递归,回到上一个格子,找寻下一条可行路径。代码如下:

void print_paths(int m, int n, int M, int N, int len){
    if(g[m][n] == 0) return;
    point p; p.x=n; p.y=m;
    vp[len++] = p;
    if(m == M && n == N){
        for(int i=0; i<len; ++i)
            cout<<"("<<vp[i].y<<", "<<vp[i].x<<")"<<" ";
        cout<<endl;
    }
    else{
        print_paths(m, n+1, M, N, len);
        print_paths(m+1, n, M, N, len);
    }
}

程序使用的输入样例8.2.in如下:

3 4
1 1 1 0
0 1 1 1
1 1 1 1

输出路径如下:

one of the paths:
(1, 1) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4) 
all paths:
(1, 1) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4) 
(1, 1) (1, 2) (1, 3) (2, 3) (3, 3) (3, 4) 
(1, 1) (1, 2) (2, 2) (2, 3) (2, 4) (3, 4) 
(1, 1) (1, 2) (2, 2) (2, 3) (3, 3) (3, 4) 
(1, 1) (1, 2) (2, 2) (3, 2) (3, 3) (3, 4)

完整代码如下:

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;

typedef long long ll;
typedef struct point{
    int x, y;
}point;
stack<point> sp;
const int MAXN = 20;
int g[MAXN][MAXN];
point vp[MAXN+MAXN];

ll path(ll m, ll n){
    if(m == 1 || n == 1) return 1;
    else return path(m-1, n) + path(m, n-1);
}
ll fact(ll n){
    if(n == 0) return 1;
    else return n*fact(n-1);
}
ll path1(ll m, ll n){
    return fact(m-1+n-1)/(fact(m-1)*fact(n-1));
}
bool get_path(int m, int n){
    point p; p.x=n; p.y=m;
    sp.push(p);
    if(n==1 && m==1) return true;
    bool suc = false;
    if(m>1 && g[m-1][n])
        suc = get_path(m-1, n);
    if(!suc && n>1 && g[m][n-1])
        suc = get_path(m, n-1);
    if(!suc) sp.pop();
    return suc;
}
void print_paths(int m, int n, int M, int N, int len){
    if(g[m][n] == 0) return;
    point p; p.x=n; p.y=m;
    vp[len++] = p;
    if(m == M && n == N){
        for(int i=0; i<len; ++i)
            cout<<"("<<vp[i].y<<", "<<vp[i].x<<")"<<" ";
        cout<<endl;
    }
    else{
        print_paths(m, n+1, M, N, len);
        print_paths(m+1, n, M, N, len);
    }
}
int main(){
    freopen("8.2.in", "r", stdin);
    for(int i=1; i<10; ++i)
        cout<<path(i, i)<<endl;
    cout<<endl;
    for(int i=1; i<10; ++i)
        cout<<path1(i, i)<<endl;
    cout<<endl;
    int M, N;
    cin>>M>>N;
    for(int i=1; i<=M; ++i)
        for(int j=1; j<=N; ++j)
            cin>>g[i][j];
    cout<<"one of the paths:"<<endl;        
    get_path(M, N);
    while(!sp.empty()){
        point p = sp.top();
        cout<<"("<<p.y<<", "<<p.x<<")"<<" ";
        sp.pop();
    }
    cout<<endl<<"all paths:"<<endl;
    print_paths(1, 1, M, N, 0);
    fclose(stdin);
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview