在C中的矩阵中找到给定起点和终点坐标的点之间的路径

nfs0ujit  于 2023-05-22  发布在  其他
关注(0)|答案(1)|浏览(142)

在下面的代码中,我尝试编写一个程序,检查是否存在从起始坐标(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;
}
o0lyfsai

o0lyfsai1#

您的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];
}

相关问题