计算在C ++中迷宫中到达目的地的方式数量
给定迷宫表示为行Xcol矩阵，其中障碍物表示为-1，并且透明单元格的值不同于-1。目标是从第一个单元格arr[0][0]开始并到达最后一个单元格arr[row][col]，以便仅允许两个移动：
向右移arr[i][j]到arr[i][j+1]和
向下移动arr[i][j]到arr[i+1][j]。
让我们通过示例来理解。
输入 -arr[row][col]={{0，0，0}，{-1，-1，0}，{0，0，0}}
输出-在迷宫中到达目的地的方式数量计数：1
解释
012
0 000
1-1-1 0
200 0
方式将是：
像元(0,0)→像元(0,1)→像元(0,2)→像元(1,2)→像元(2,0)
输入 -arr[row][col]={{0，0，0，0}，{-1，0，-1，0}，{-1，0，-1，0}，{0，0，0，0}}
输出-在迷宫中到达目的地的方式数量计数：2
解释
0123
0 0000
1-1 0 -1 0
2-1 0 -1 0
30 0 0 0
方式将是：
像元(0,0)→像元(0,1)→像元(1,1)→像元(2,1)→像元(3,1)→像元(3,2)→像元(3,3)
像元(0,0)→像元(0,1)→像元(0,2)→像元(0,3)→像元(1,3)→像元(2,3)→像元(3,3)
以下程序中使用的方法如下
在这种方法中，我们首先将所有零设置为1。再次遍历迷宫矩阵，现在遍历每个单元格（如果是阻塞(-1)，则忽略它）。如果不是，则检查上部单元格(i-1,j)和左侧单元格(i,j-1)。如果大于零，则将其值添加到当前单元格(i,j)。这样，我们将在单元格(row-1,col-1)上获得总和，作为达到该总和的方法。
以输入数组arr[row][col]作为迷宫。
函数destination_maze（intarr[row][col]）接受arr并返回迷宫中到达目的地的方式数。
如果第一个单元格被阻塞，则返回0作为到达终点的方式。
现在遍历最左边的列，并将所有0设置为1。首先，由于无法到达其下方的单元格，因此阻塞使循环中断。从索引i=0到i<row开始，如果arr[i][0]为0，则将其设置为1。
类似地，对从j=0到j<col的第一行进行处理，如果arr[j][0]为0，则将其设置为1。
再次遍历单元格(1,1)的arr，如果arr[i][j]为-1，则不执行任何操作。
如果arr[i-1][j]或arr[i][j-1]大于0，则可以从它们到达arr[i][j]。因此，为其增加价值。
最后，我们将获得arr[row-1][col-1]作为达到它的全部方法。
如果>0，则返回0，否则返回0。
示例
#include<bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
int destination_maze(int arr[row][col]) {
if (arr[0][0] == -1) {
return 0;
}
for (int i = 0; i < row; i++) {
if (arr[i][0] == 0) {
arr[i][0] = 1;
} else {
break;
}
}
for (int i = 1; i < col; i++) {
if (arr[0][i] == 0) {
arr[0][i] = 1;
} else {
break;
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (arr[i][j] == -1) {
continue;
}
if (arr[i - 1][j] > 0) {
arr[i][j] = (arr[i][j] + arr[i - 1][j]);
}
if (arr[i][j - 1] > 0) {
arr[i][j] = (arr[i][j] + arr[i][j - 1]);
}
}
}
if (arr[row - 1][col - 1] > 0) {
return arr[row - 1][col - 1];
} else {
return 0;
}
}
int main() {
int arr[row][col] = {
{
0,
0,
0
},
{
-1,
-1,
0
},
{
0,
0,
0
}
};
cout << "在迷宫中到达目的地的方式数量如下： " << destination_maze(arr);
return 0;
}如果我们运行上面的代码，它将生成以下输出-
输出结果
在迷宫中到达目的地的方式数量如下： 1