给一个h×m的网格,一开始在左上角 (1,1) 每一步只能向右或向下走,不能经过 '#' 格子,求走到右下角(h,m)有多少种走法。 ,请说出下列代码不能输出该问题正确结果的原因,并改正次代码,并且对每条语句进行注释
时间: 2024-02-24 08:57:18 浏览: 11
以下是有问题的代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int dp[n+1]={0};//定义一个一维数组
dp[1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
if(x==1)
dp[j]=0;//如果有障碍物,将该格子的路径数设为 0
else
dp[j]+=dp[j-1];//状态转移方程
}
cout<<dp[m]<<endl;//输出答案
return 0;
}
```
代码的问题在于,定义的是一维数组 `dp`,但是在计算时却没有正确处理二维网格的行列关系。具体来说,`dp[j]` 表示的是从起点到第 i 行第 j 列的位置的不同路径数,但是在计算时却没有按照二维网格的行列关系来更新 `dp` 数组,而是直接把 `dp[j]` 当成了第 j 列的路径数,忽略了行的信息。因此,需要将 `dp` 数组的定义改为二维数组,并按照二维网格的行列关系来更新数组。
以下是改正后的代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int dp[n+1][m+1]={0};//定义一个二维数组
dp[1][1]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
if(x==1)
dp[i][j]=0;//如果有障碍物,将该格子的路径数设为 0
else
dp[i][j]=dp[i-1][j]+dp[i][j-1];//状态转移方程
}
cout<<dp[n][m]<<endl;//输出答案
return 0;
}
```
这里将 `dp` 数组定义为二维数组,并按照二维网格的行列关系来更新数组。同时,将输出 `dp[n][m]`。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)