給定矩陣單元格到所有其他單元格的最小距離

---

在這個問題中，我們需要找到矩陣中每個單元格到給定單元格的距離。

我們將使用廣度優先搜尋遍歷來從給定單元格訪問矩陣的每個單元格，並找到每個單元格的最小距離。

問題陳述 - 我們給定行數 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 中，當我們逐個訪問每個節點的相鄰節點時。因此，當我們第一次到達特定單元格時，它總是給出最小距離。