Finding a way between points given start and end coordinates in the matrix in C

Question

In the code below, I tried to write a program that checks whether there is a path consisting of 0s from the starting coordinate (sx,sy) to (dx,dy). For instances from (0,0) to (3,3) there seems to be a path of 0s and the output should be true. But I am not getting the correct result. It doesn't work the way I want. Can you help me to find my mistake?

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

Have you tried running your code line-by-line in a debugger while monitoring the control flow and the values of all variables, in order to determine in which line your program stops behaving as intended? If you did not try this, then you may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Andreas Wenzel, May 19 '23 at 22:37
I suspect your algorithm doesn't even really start, because `matrix[sx][sy] != 0`, so it just immediately returns. Ditto `matrix[dx][dy]` will never be visited, for the same reason. — pmacfarlane, May 19 '23 at 23:04
Aside: `if (!visited[dx][dy]) return false; else return true;` is a really complicated way of saying `return visited[dx][dy];` — pmacfarlane, May 19 '23 at 23:12
Yes, you're right, I found where the error is. dfs(adj, sx, sy, visited)'; here the dfs function will not start at all due to the 'adj[sx][sy]!=0' condition. So I need to change the condition for the starting point to be different from 0. Do you have any idea about this? — alperone12, May 19 '23 at 23:20
You would probably need to remove the test for `adj[i][j] != 0` in the bit that returns, and then only visit neighbours which are `0`, i.e. for each of your recursions into neighbours, you only call them if they are `0`. Your final test would be that a neighbour of `[dx][dy]` was visited, not that the actual destination was visited. — pmacfarlane, May 19 '23 at 23:29
Or, and this might "just work"... just set your `[sx][sy]`and `[dx][dy]` to `0` before you start the search. Your algorithm might then work as-is. — pmacfarlane, May 19 '23 at 23:32
Actually, what I want to do is create a way that combines 2 repeating numbers using 0 value cells and replace the 0 values in between with that number. The last situation you said came to my mind, but if I set the value (sx,sy) to 0, I cannot replace the 0s in the path with the number at the starting point. — alperone12, May 19 '23 at 23:38
I've posted an answer to the question posed. I think if your requirements are different, you should post a new question. — pmacfarlane, May 19 '23 at 23:43
Thank you for your responses. You have been very helpful in finding the error and generating ideas about solutions. — alperone12, May 19 '23 at 23:43
In fact, my aim was to ensure that this program finds a path between the two given coordinates and then develop it for my purpose. Once I fix this bug, if I come across any new bugs, I'll post it as a new question. — alperone12, May 19 '23 at 23:46

score 0 · Accepted Answer · answered May 19 '23 at 23:43

Your void dfs() function looks almost correct. However, it immediately returns if the matrix entry at [i][j] is not zero.

Your code has a start position of [0][0], and the matrix entry there is 1. Therefore your search doesn't even begin, it just immediately fails because the start location does not have 0 in it.

For the same reason, your destination position [3][3] will never be visited, because it contains the value 2.

The simplest solution would be to manually set the start and end positions to have the value 0 before starting the search:

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

Thank you very much for your reply. You helped me fix my mistake and now my program is working. For example, let the value at the starting point be 2. How can I replace all the 0 values in between with the number at the starting point after finding the path? — alperone12, May 19 '23 at 23:56
@alperone12 You should post a new question with your new code to ask that question. — pmacfarlane, May 19 '23 at 23:58

Finding a way between points given start and end coordinates in the matrix in C

1 Answers1