题解 | #填数游戏#

走网格

http://www.nowcoder.com/practice/aeb113f9081d4b97b78696f31b20dde7

题意：

给你一个大小为 $n*m$ 的网格图，其中有一块矩形区域（左上角位置为 $(x0,y0)$ ，右下角位置为 $(x1,y1)$ ）不能走，起点在 $(1,1)$ 处，每次你只能向右或者向下走，问最后走到终点 $(n,m)$ 有多少种方案？

解法一（DFS暴力枚举，不可AC）

我们可以用深度优先搜索算法枚举所有的路线，并且统计答案。

具体的：

我们用递归函数 $dfs(i,j)$ 表示当前走到点 $(i,j)$ ，接下来我们开始讨论：

1. 点 $(i,j)$ 超出网格图范围，直接返回

2. 点 $(i,j)$ 处在不可走的矩形区域范围，直接返回

3. 点 $(i,j)$ 处在终点 $(n,m)$ 处，答案+1并返回

4. 其他情况，分别扩展向右走和向下走两种情况，即 $dfs(i,j+1)$ 和 $dfs(i+1,j)$

代码：

class Solution {
public:
    const int mod=1e9+7;
    int n,m,x0,y0,x1,y1;
    inline bool check(int i,int j){
        //判断点(i,j)是否不在矩形区域内
        return i<x0||j<y0||i>x1||j>y1;
    }
    int ans;
    void dfs(int i,int j){
        if(i<=0||i>n||j<=0||j>m||!check(i,j))return;//前两种情况
        if(i==n&&j==m){
            ans=(ans+1)%mod;//第三种情况
            return;
        }
        //其他情况，直接扩展
        dfs(i,j+1);
        dfs(i+1,j);
    }
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        this->n=n,this->m=m,this->x0=x0,this->y0=y0,this->x1=x1,this->y1=y1;
        this->ans=0;
        dfs(1,1);//从起点开始扩展
        return ans;
    }
};

时间复杂度： $O(2^{n*m})$ ，对于每个格子，有两种决策（向右走和向下走），根据乘法原理可得方案数为 $O(2^{n*m})$ 级别，故总的时间复杂度为 $O(2^{n*m})$
空间复杂度： $O(n+m)$ ，路线长度为 $n+m-1$ ，故递归深度为 $O(n+m)$ 级别，故空间复杂度为 $O(n+m)$

解法二（动态规划）

我们设 $f[i][j]$ 表示从起点 $(1,1)$ 走到点 $(i,j)$ 的方案数，接下来我们分情况讨论：

1. 显然 $f[1][1]=1$

2. 若点 $(i,j)$ 处在矩形范围内，则 $f[i][j]=0$

3. 其他情况我们考虑，每个点只会从上面下来和从左边过来

则我们有 $f[i][j]=f[i][j-1]+f[i-1][j]$

最后答案即为 $f[n][m]$

代码：

class Solution {
public:
    const int mod=1e9+7;
    inline bool check(int i,int j,int x0,int y0,int x1,int y1){
        //判断点(i,j)是否可走
        return i<x0||i>x1||j<y0||j>y1;
    }
    int f[1005][1005];
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        f[1][1]=1;//起点状态
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(i==1&&j==1)continue;//起点状态已经计算过了
                if(check(i,j,x0,y0,x1,y1)){
                    //当前点可以走
                    f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
                }
            }
        }
        return f[n][m];//最后答案
    }
};