C++ 从给定单元格到矩阵中所有其他单元格的最小距离

在这个问题中，我们需要找到矩阵中每个单元格与给定单元格之间的距离。

我们将使用广度优先搜索遍历来访问矩阵中的每个单元格，从给定单元格开始，并找到每个单元格的最小距离。

问题陈述 −我们给定正整数rows、cols、a和b。这里，rows和cols表示矩阵的总行数和列数。a和b是矩阵的单元格。我们需要找到矩阵中每个单元格到（a,b）单元格的最小距离。

示例

输入

rows = 6, cols = 6, a = 3, b = 3

输出

3 3 3 3 3 3 
3 2 2 2 2 2 
3 2 1 1 1 2 
3 2 1 0 1 2 
3 2 1 1 1 2 
3 2 2 2 2 2

解释 - 我们已经打印出了每个单元格距离(3, 3)单元格的距离。

输入

rows = 2, cols = 2, a = 0, b = 0;

输出

0 1 
1 1

解释 - 每个单元格的距离从(0, 0)单元格为1。

方法

在这里，我们将使用队列来存储每个访问过的单元格。之后，我们将从队列中弹出每一对，并在所有8个方向上遍历，以找到基于当前单元格距离(a, b)节点的其他最近单元格的距离。

步骤

步骤1 - 定义变量t1和t2，并将它们初始化为变量a和b的值。

步骤2 - 定义direX[]和direY[]数组，用于存储从当前单元格出发的每个可能的方向。

步骤3 - 定义队列，用于存储矩阵单元格的一对。

步骤4 - 将{a, b}对插入队列，并将矩阵[a][b]初始化为0。

步骤5 - 遍历队列。

步骤5.1 - 在循环中弹出队列的第一个对。

步骤5.2 - 遍历direX[]和direY[]数组，以在所有8个方向上移动。

步骤5.2.1 - 将a + direX[p]存储到temp_x变量中，并将b + direY[p]存储到temp_y变量中。

步骤5.2.2 - 如果temp_x, temp_y小于0或temp_x大于cols，或temp_y大于rows，则进入下一次迭代。

步骤5.2.3 - 如果matrix[temp_x][temp_y]为0，则使用matrix[a][b] + 1更新它。还要将更新后的对插入队列。

步骤6 - 使用0更新matrix[t1][t2]。

步骤7 - 打印矩阵值。

示例

#include <bits/stdc++.h>
using namespace std;

int matrix[1001][1001];
void getMinDistance(int rows, int cols, int a, int b) {
    int t1 = a, t2 = b;
    // All directions
    int direX[] = {0, -1, -1, -1, 0, 1, 1, 1};
    int direY[] = {1, 1, 0, -1, -1, -1, 0, 1};
    queue<pair<int, int>> que;
    // Push the first pair to the queue
    que.push({a, b});
    matrix[a][b] = 0;
    while (!que.empty()) {
        // Get pair from top of the queue
        a = que.front().first;
        b = que.front().second;
        // Pop them
        que.pop();
        for (int p = 0; p < 8; p++) {
            int temp_x = a + direX[p];
            int temp_y = b + direY[p];
            // Boundary index validation
            if (temp_x < 0 || temp_x >= rows || temp_y >= cols || temp_y < 0)
                continue;
            // For non-visited cells
            if (matrix[temp_x][temp_y] == 0) {
                // Update minimum distance
                matrix[temp_x][temp_y] = matrix[a][b] + 1;
                // Insert new pair to queue
                que.push({temp_x, temp_y});
            }
        }
    }
    matrix[t1][t2] = 0;
    for (int p = 0; p < rows; p++) {
        for (int q = 0; q < cols; q++) {
            cout << matrix[p][q] << " ";
        }
        cout << endl;
    }
}
int main() {
    int rows = 6, cols = 6, a = 3, b = 3;
    getMinDistance(rows, cols, a, b);
}

输出

3 3 3 3 3 3 
3 2 2 2 2 2 
3 2 1 1 1 2 
3 2 1 0 1 2 
3 2 1 1 1 2 
3 2 2 2 2 2

时间复杂度 – 创建矩阵的复杂度为O(行数*列数)。

空间复杂度 – 复杂度为O(行数*列数)。

在这里，我们使用BFS算法与矩阵一起找到每个单元格从源单元格到达的最小距离。在BFS中，当我们逐个访问每个节点的相邻节点时，总是给出第一次到达特定单元格时的最小距离。