在下面的代码中,我尝试编写一个程序,检查是否存在从起始坐标(sx,sy)到(dx,dy)的由0组成的路径。例如,从(0,0)到(3,3)似乎有一条0的路径,输出应该为真。但我没有得到正确的结果。它不像我想要的那样工作。你能帮我找出我的错误吗?
#include <stdio.h>
#include <stdbool.h>
#define N 5
void dfs(int adj[][N], int i, int j, bool visited[][N]);
bool hasPathDfs(int adj[][N], int sx, int sy, int dx, int dy);
int main()
{
int matrix[N][N] = {
{1, 0, 0, 0, 0},
{2, 3, 0, 3, 1},
{0, 4, 0, 0, 0},
{0, 0, 0, 2, 4},
{5, 0, 0, 2, 5}};
// Find path
int sx = 0, sy = 0, dx = 3, dy = 3;
printf("Find path from (%d,%d) to (%d,%d):\n", sx, sy, dx, dy);
printf("DFS: %s\n", hasPathDfs(matrix, sx, sy, dx, dy) ? "true" : "false");
return 0;
}
// Function Declarations
void dfs(int adj[][N], int i, int j, bool visited[][N])
{
if (i < 0 || i >= N || j < 0 || j >= N || adj[i][j] != 0 || visited[i][j])
{
return;
}
visited[i][j] = true;
dfs(adj, i - 1, j, visited); // Move left
dfs(adj, i + 1, j, visited); // Move Right
dfs(adj, i, j - 1, visited); // Move top
dfs(adj, i, j + 1, visited); // Move bottom
}
bool hasPathDfs(int adj[][N], int sx, int sy, int dx, int dy)
{
bool visited[N][N];
int i,j;
for ( i = 0; i < N; i++)
{
for ( j = 0; j < N; j++)
{
visited[i][j] = false;
}
}
dfs(adj, sx, sy, visited);
if (!visited[dx][dy])
{
return false;
}
return true;
}
1条答案
按热度按时间o0lyfsai1#
您的
void dfs()
函数看起来几乎是正确的。但是,如果[i][j]
处的矩阵项不为零,则它会立即返回。代码的起始位置为
[0][0]
,矩阵项为1
。因此,您的搜索甚至没有开始,它只是立即失败,因为开始位置没有0
。出于同样的原因,您的目标位置
[3][3]
永远不会被访问,因为它包含值2
。最简单的解决方案是在开始搜索之前手动将开始和结束位置设置为值
0
: