给定起始坐标和结束坐标，更改矩阵中两点之间路径上的值

Question

在下面的代码中，有一段代码是在给定起始坐标和结束坐标的两点之间寻找是否存在由0数组成的路径。但是找到路径后，我想用起点处的值替换这条路径中的0值。我怎样才能达到这种情况？

#include <stdio.h>
#include <stdbool.h>

#define M 4
#define N 5
void dfs(int adj[][N], int i, int j, bool visited[][N])
{
    if (i < 0 || i >= M || 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;
        }
    }

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



int main()
{
    // 2D matrix with 1's as blocked and 0's as path.
    int matrix[M][N] = {
        {0, 0, 1, 0, 1},
        {1, 2, 5, 0, 0},
        {0, 0, 2, 0, 1},
        {0, 5, 0, 0, 0}};
  
    // Find path
    int sx = 1, sy = 2, dx = 3, dy = 1;
    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;
}

Answer 1

您只需要从起始位置读取值，并将其传递给查找路径的递归函数。每次将

visited

设置为 true 时，将该值存储到其中。

void dfs(int adj[][N], int i, int j, bool visited[][N], int poison)
{
    if (i < 0 || i >= M || j < 0 || j >= N || adj[i][j] != 0 || visited[i][j])
    {
        return;
    }
    visited[i][j] = true;
    adj[i][j] = poison;

    dfs(adj, i - 1, j, visited, poison); // Move left
    dfs(adj, i + 1, j, visited, poison); // Move Right
    dfs(adj, i, j - 1, visited, poison); // Move top
    dfs(adj, i, j + 1, visited, poison); // 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;
        }
    }

    int poison = adj[sx][sy];

    // 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, poison);

    return visited[dx][dy];
}