在下面的代码中,我try 编写一个程序来判断从起始坐标(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;
}


推荐答案

您的void dfs()函数看起来几乎正确.然而,如果[i][j]处的矩阵条目不为零,则它立即返回.

您的代码的起始位置是[0][0],那里的矩阵条目是1.因此,您的搜索甚至没有开始,它只是立即失败,因为开始位置没有0.

出于同样的原因,您的目的地位置[3][3]将永远不会被访问,因为它包含值2.

最简单的解决方案是在开始搜索之前将开始位置和结束位置手动设置为值0:

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;
        }
    }

    // Mark the start and end positions as part of the '0' trail
    adj[sx][sy] = 0;
    adj[dx][dy] = 0;

    dfs(adj, sx, sy, visited);

    return visited[dx][dy];
}

C++相关问答推荐

两个看似相同的代码的不同行为

Bison解析器转移/减少冲突

Pure Win32 C(++)-除了替换控件的窗口程序之外,还有其他方法可以在输入时禁用按钮吗?

字符数组,字符指针,在一种情况下工作,但在另一种情况下不工作?

在C中将通用字符名称转换为UTF-8

C由四个8位整数组成无符号32位整数

如何将字符串传递给函数并返回在C中更改的相同字符串?

如何在不使用其他数组或字符串的情况下交换字符串中的两个单词?

如何在CANbus RX/TX FIFO起始地址寄存器(ATSAME 51)的特定地址初始化数组?

S将C语言宏定义为自身的目的是什么?(在glibc标题中看到)

RawMotion的XInput2错误(具有较高值的XISelectEvents上的BadValue)

关于scanf()和空格的问题

通过k&;r语法的c声明无效

如何组合两个宏来初始化C语言中的字符串数组?

C23标准是否向后兼容?

用C++初始化局部数组变量

被调用方函数内部的C-Struct变量,它是指针还是无关紧要

变量值不正确的问题

解密Chrome加密密钥

C Makefile - 如何避免重复提及文件名