题解 | #填数游戏#
走网格
http://www.nowcoder.com/practice/aeb113f9081d4b97b78696f31b20dde7
题意：
给你一个大小为
的网格图，其中有一块矩形区域（左上角位置为)
，右下角位置为)
）不能走，起点在)
处，每次你只能向右或者向下走，问最后走到终点)
有多少种方案？
解法一（DFS暴力枚举，不可AC）
我们可以用深度优先搜索算法枚举所有的路线，并且统计答案。
具体的：
我们用递归函数)
表示当前走到点)
，接下来我们开始讨论：
1. 点超出网格图范围，直接返回
2. 点处在不可走的矩形区域范围，直接返回
3. 点处在终点处，答案+1并返回
4. 其他情况，分别扩展向右走和向下走两种情况，即)
和)
代码：
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;
}
}; 时间复杂度：空间复杂度：
解法二（动态规划）
我们设
表示从起点走到点的方案数，接下来我们分情况讨论：
1. 显然
2. 若点处在矩形范围内，则
3. 其他情况我们考虑，每个点只会从上面下来和从左边过来
则我们有
最后答案即为
代码：
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];//最后答案
}
}; 时间复杂度： 空间复杂度：)
，我们需要用一个大小为的二维数组保存状态，故总的空间复杂度为
华为工作强度 823人发布