. Matriks

542. 01 Matriks

Kesukaran: Sederhana

Topik: Tatasusunan, Pengaturcaraan Dinamik, Breadth-First Search, Matriks

Diberikan tikar matriks binari m x n, kembalikan jarak 0 terdekat untuk setiap sel.

Jarak antara dua sel yang berkongsi tepi sepunya ialah 1.

Contoh 1:

• Input: tikar = [[0,0,0],[0,1,0],[0,0,0]]
• Output: [[0,0,0],[0,1,0],[0,0,0]]

Contoh 2:

• Input: tikar = [[0,0,0],[0,1,0],[1,1,1]]
• Output: [[0,0,0],[0,1,0],[1,2,1]]

Kekangan:

• m == tikar.panjang
• n == tikar[i].panjang
• 1 4
• 1 4
• mat[i][j] ialah sama ada 0 atau 1.
• Terdapat sekurang-kurangnya satu 0 dalam tikar.

Nota: Soalan ini sama dengan 1765. Peta Puncak Tertinggi

Penyelesaian:

Kami akan menggunakan Breadth-First Search (BFS) berbilang sumber, di mana semua 0 sel dianggap sebagai titik permulaan (sumber). Untuk setiap 1 sel, kami mengira jarak minimum ke 0 terdekat.

Mari laksanakan penyelesaian ini dalam PHP: 542. 01 Matriks

<?php /**
 * @param Integer[][] $mat
 * @return Integer[][]
 */
function updateMatrix($mat) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$mat1 = [[0,0,0],[0,1,0],[0,0,0]];
$mat2 = [[0,0,0],[0,1,0],[1,1,1]];

echo updateMatrix($mat1) . "\n"; // Output: [[0,0,0],[0,1,0],[0,0,0]]
echo updateMatrix($mat2) . "\n"; // Output: [[0,0,0],[0,1,0],[1,2,1]]
?>

Penjelasan:

1. Permulaan:

   • tatasusunan jarak dimulakan dengan PHP_INT_MAX untuk semua sel pada mulanya.
   • Semua 0 sel ditetapkan kepada 0 dalam tatasusunan jarak dan ditambahkan pada baris gilir BFS.

2. BFS Berbilang Sumber:

   • Dengan menggunakan baris gilir, kami melakukan BFS daripada semua 0 sel serentak.
   • Untuk setiap sel dalam baris gilir, semak jirannya (atas, bawah, kiri, kanan).
   • Jika jarak jiran boleh dikurangkan (jarak[newRow][newCol] > currentDistance 1), kemas kini jaraknya dan masukkannya.

3. Output:

   • Tatasusunan jarak dikemas kini dengan jarak minimum ke 0 terdekat untuk semua sel.

Input dan Output:

Input 1:

$mat1 = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];

Output 1:

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 0
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )
)

Input 2:

$mat2 = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1]
];

Output 2:

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 0
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 1
        )
)

Penyelesaian ini cekap dengan kerumitan masa O(m × n), kerana setiap sel diproses sekali. Kerumitan ruang juga O(m × n) disebabkan tatasusunan jarak dan baris gilir BFS.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci . Matriks. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!