刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

回家的路

小 Z 家所在的街道都是横平竖直的，从空中俯视看，非常像一张方格表，由 n 行 m 列的方格组成 ，而小 Z 此刻正站在最左上角的格子中，想走回到最右下角的家中，他每次只能往右或者往下走一个格子，毕竟不能走回头路。

由于小 Z 家附近在修路，就导致有些格子还不能走。 好在小 Z 手上有一份地图，标注了哪些格子能走，哪些格子不能走。现在请你帮小 Z 算算他这次回家一共有多少种走法吧~

【输入格式】

共 n + 1 行，

第 1 行为 2 个正整数 n、m，用空格隔开，表示方格表的行数和列数；

第 2 ~ n+1 行为地图，每行为 m-1 个用空格隔开的正整数 0 或 1，0 表示不能走，1 表示能走。

【输出格式】

一行，一个数，表示小 Z 回家可选的路线总数。


【输入样例】

3 4

1 0 1 1

1 1 1 1

1 1 1 1

【输出样例】

4

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```#include#includeusing namespace std;int uniquePaths(vector>& grid) int n = grid.size();int m = grid[0].size();vector> dp(n, vector(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) {if (i == 0 || j == 0) {dp[i][j] = 1;} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}}return dp[n - 1][m - 1];int main() int n, m;cin >> n >> m;vector> grid(n, vector(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m - 1; j++) {cin >> grid[i][j];}}cout << uniquePaths(grid) << endl;return 0;```

解析：

【喵呜刷题小喵解析】：

本题可以使用动态规划来解决。

首先，我们定义一个二维数组dp[i][j]，其中dp[i][j]表示从起点到位置(i, j)的方案数。

然后，我们从起点开始，遍历整个地图。对于每个位置(i, j)，如果当前位置可以走（即grid[i][j] == 1），则有两种走法：从位置(i-1, j)走到当前位置，或者从位置(i, j-1)走到当前位置。因此，dp[i][j] = dp[i-1][j] + dp[i][j-1]。

最后，dp[n-1][m-1]即为从起点到终点的方案数，即为所求。

在主函数中，我们首先从输入中读取地图，然后调用uniquePaths函数求解方案数，并输出结果。
创作类型：
原创

本文链接：回家的路 小 Z 家所在的街道都是横平竖直的，从空中俯视看，非常像一张方格表，由 n 行 m 列的方

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share