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

---

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

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

问题陈述 - 我们给定行数 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} 插入队列，并将 matrix[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 - 将 matrix[t1][t2] 更新为 0。

步骤 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(rows*cols) 用于创建矩阵。

空间复杂度 - O(rows * cols)

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