为什么下面的代码 returns 计数值错误?
Why does the following code returns wrong value of count?
问题:
给定一个 n x m 的二维矩阵。矩阵包含整数。给定一个目的地位置,找到满足以下条件的人可以从源(起点)到达目的地的方式的数量 -
(i) 只能向北、南、东或西方向移动。
(ii) 当且仅当该单元格的值小于当前单元格中的值时,一个人才能从一个单元格移动到另一个单元格。
#include<iostream>
using namespace std;
void printSolution(int** solution, int n, int m)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<solution[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
int mazeHelp(int** maze, int** solution, int x, int y, int desx, int desy, int n, int m)
{
int count = 0;
if(x==desx-1 && y==desy-1)
{
solution[x][y] = 1;
printSolution(solution, n, m);
count++;
solution[x][y]=0;
//cout<<"Return 1"<<endl;
return count;
}
if(x<0 || y<0 || x>=desx || y>=desy || solution[x][y]==1)
{
//cout<<"Return 2"<<endl;
return count;
}
solution[x][y] = 1;
if(x+1<desx && solution[x+1][y]!=1 && maze[x+1][y]>maze[x][y])
{
count = mazeHelp(maze, solution, x+1, y, desx, desy, n, m);
}
if(x-1>0 && solution[x-1][y]!=1 && maze[x-1][y]>maze[x][y])
{
count = mazeHelp(maze, solution, x-1, y, desx, desy, n, m);
}
if(y+1<desy && solution[x][y+1]!=1 && maze[x][y+1]>maze[x][y])
{
count = mazeHelp(maze, solution, x, y+1, desx, desy, n, m);
}
if(y-1>0 && solution[x][y-1]!=1 && maze[x][y-1]>maze[x][y])
{
count = mazeHelp(maze, solution, x, y-1, desx, desy, n, m);
}
solution[x][y] = 0;
}
int printPaths(int** maze, int desx, int desy, int** solution, int n, int m)
{
int count = 0;
count = mazeHelp(maze, solution, 0, 0, desx, desy, n, m);
return count;
}
int main()
{
int desx, desy, n, m;
cout<<"Enter number of rows : ";
cin>>n;
cout<<"Enter number of columns : ";
cin>>m;
cout<<"Enter matrix : "<<endl;
int** solution = new int*[n];
for(int i=0;i<n;i++){
solution[i] = new int[m];
}
int** maze = new int*[m];
for(int i=0;i<n;i++){
maze[i] = new int[m];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>maze[i][j];
}
}
for(int i=0; i<n; i++)
{
for(int j=0;j<m;j++)
{
solution[i][j] = 0;
}
}
cout<<"Enter destination address (x,y) : ";
cin>>desx>>desy;
int res = printPaths(maze, desx, desy, solution, n, m);
cout<<"Total number of paths : "<<res;
return 0;
}
我的代码为每个输入打印正确的路径,但 return 每次都打印错误的计数值。路径数计算有没有错误?
正如评论中已经提到的,在 mazeHelp
函数中,您在多个地方递归调用 mazeHelp
。每次调用 returns 找到一些路径。您必须将它们累积在 count
变量中,并且 return 最后 count
用于父递归调用。
int mazeHelp(int** maze, int** solution, int x, int y, int desx, int desy, int n, int m)
{
int count = 0;
if(x==desx-1 && y==desy-1)
{
solution[x][y] = 1;
printSolution(solution, n, m);
count++;
solution[x][y]=0;
//cout<<"Return 1"<<endl;
return count;
}
if(x<0 || y<0 || x>=desx || y>=desy || solution[x][y]==1)
{
//cout<<"Return 2"<<endl;
return count;
}
solution[x][y] = 1;
if(x+1<desx && solution[x+1][y]!=1 && maze[x+1][y]>maze[x][y])
{
count += mazeHelp(maze, solution, x+1, y, desx, desy, n, m);
}
if(x-1>0 && solution[x-1][y]!=1 && maze[x-1][y]>maze[x][y])
{
count += mazeHelp(maze, solution, x-1, y, desx, desy, n, m);
}
if(y+1<desy && solution[x][y+1]!=1 && maze[x][y+1]>maze[x][y])
{
count += mazeHelp(maze, solution, x, y+1, desx, desy, n, m);
}
if(y-1>0 && solution[x][y-1]!=1 && maze[x][y-1]>maze[x][y])
{
count += mazeHelp(maze, solution, x, y-1, desx, desy, n, m);
}
solution[x][y] = 0;
return count;
}
问题: 给定一个 n x m 的二维矩阵。矩阵包含整数。给定一个目的地位置,找到满足以下条件的人可以从源(起点)到达目的地的方式的数量 - (i) 只能向北、南、东或西方向移动。 (ii) 当且仅当该单元格的值小于当前单元格中的值时,一个人才能从一个单元格移动到另一个单元格。
#include<iostream>
using namespace std;
void printSolution(int** solution, int n, int m)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cout<<solution[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
int mazeHelp(int** maze, int** solution, int x, int y, int desx, int desy, int n, int m)
{
int count = 0;
if(x==desx-1 && y==desy-1)
{
solution[x][y] = 1;
printSolution(solution, n, m);
count++;
solution[x][y]=0;
//cout<<"Return 1"<<endl;
return count;
}
if(x<0 || y<0 || x>=desx || y>=desy || solution[x][y]==1)
{
//cout<<"Return 2"<<endl;
return count;
}
solution[x][y] = 1;
if(x+1<desx && solution[x+1][y]!=1 && maze[x+1][y]>maze[x][y])
{
count = mazeHelp(maze, solution, x+1, y, desx, desy, n, m);
}
if(x-1>0 && solution[x-1][y]!=1 && maze[x-1][y]>maze[x][y])
{
count = mazeHelp(maze, solution, x-1, y, desx, desy, n, m);
}
if(y+1<desy && solution[x][y+1]!=1 && maze[x][y+1]>maze[x][y])
{
count = mazeHelp(maze, solution, x, y+1, desx, desy, n, m);
}
if(y-1>0 && solution[x][y-1]!=1 && maze[x][y-1]>maze[x][y])
{
count = mazeHelp(maze, solution, x, y-1, desx, desy, n, m);
}
solution[x][y] = 0;
}
int printPaths(int** maze, int desx, int desy, int** solution, int n, int m)
{
int count = 0;
count = mazeHelp(maze, solution, 0, 0, desx, desy, n, m);
return count;
}
int main()
{
int desx, desy, n, m;
cout<<"Enter number of rows : ";
cin>>n;
cout<<"Enter number of columns : ";
cin>>m;
cout<<"Enter matrix : "<<endl;
int** solution = new int*[n];
for(int i=0;i<n;i++){
solution[i] = new int[m];
}
int** maze = new int*[m];
for(int i=0;i<n;i++){
maze[i] = new int[m];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>maze[i][j];
}
}
for(int i=0; i<n; i++)
{
for(int j=0;j<m;j++)
{
solution[i][j] = 0;
}
}
cout<<"Enter destination address (x,y) : ";
cin>>desx>>desy;
int res = printPaths(maze, desx, desy, solution, n, m);
cout<<"Total number of paths : "<<res;
return 0;
}
我的代码为每个输入打印正确的路径,但 return 每次都打印错误的计数值。路径数计算有没有错误?
正如评论中已经提到的,在 mazeHelp
函数中,您在多个地方递归调用 mazeHelp
。每次调用 returns 找到一些路径。您必须将它们累积在 count
变量中,并且 return 最后 count
用于父递归调用。
int mazeHelp(int** maze, int** solution, int x, int y, int desx, int desy, int n, int m)
{
int count = 0;
if(x==desx-1 && y==desy-1)
{
solution[x][y] = 1;
printSolution(solution, n, m);
count++;
solution[x][y]=0;
//cout<<"Return 1"<<endl;
return count;
}
if(x<0 || y<0 || x>=desx || y>=desy || solution[x][y]==1)
{
//cout<<"Return 2"<<endl;
return count;
}
solution[x][y] = 1;
if(x+1<desx && solution[x+1][y]!=1 && maze[x+1][y]>maze[x][y])
{
count += mazeHelp(maze, solution, x+1, y, desx, desy, n, m);
}
if(x-1>0 && solution[x-1][y]!=1 && maze[x-1][y]>maze[x][y])
{
count += mazeHelp(maze, solution, x-1, y, desx, desy, n, m);
}
if(y+1<desy && solution[x][y+1]!=1 && maze[x][y+1]>maze[x][y])
{
count += mazeHelp(maze, solution, x, y+1, desx, desy, n, m);
}
if(y-1>0 && solution[x][y-1]!=1 && maze[x][y-1]>maze[x][y])
{
count += mazeHelp(maze, solution, x, y-1, desx, desy, n, m);
}
solution[x][y] = 0;
return count;
}