Memusingkan Kotak

1861. Memusingkan Kotak

Kesukaran: Sederhana

Topik: Tatasusunan, Dua Penunjuk, Matriks

Anda diberi matriks m x n kotak aksara yang mewakili pandangan sisi kotak. Setiap sel kotak adalah salah satu daripada yang berikut:

• Sebatang '#'
• Halangan pegun '*'
• Kosongkan '.'

Kotak itu dipusingkan 90 darjah mengikut arah jam, menyebabkan beberapa batu jatuh akibat graviti. Setiap batu jatuh ke bawah sehingga ia mendarat di atas halangan, batu lain, atau bahagian bawah kotak. Graviti tidak menjejaskan kedudukan halangan, dan inersia daripada putaran kotak tidak menjejaskan kedudukan mendatar batu.

Memang dijamin bahawa setiap batu di dalam kotak terletak pada halangan, batu lain atau bahagian bawah kotak.

Pulangan matriks n x m yang mewakili kotak selepas putaran yang diterangkan di atas.

Contoh 1:

• Input: kotak = [["#",".","#"]]
• Output: [["."], ["#"], ["#"]]

Contoh 2:

• Input: kotak = [["#",".","","."], ["#","#","","."] ]
• Output: [["#","."], ["#","#"], ["",""], [".",". "]]

Contoh 3:

• Input: kotak = [["#","#","",".","","."], ["#","#", "#","*",".","."], ["#","#","#",".","#","."]]
• Output: [[".","#","#"], [".","#","#"], ["#","#"," "], ["#","","."], ["#",".","*"], ["#",".","."]]

Kekangan:

• m == kotak.panjang
• n == kotak[i].panjang
• 1 <= m, n <= 500
• kotak[i][j] ialah sama ada '#', '*' atau '.'.

Petunjuk:

1. Putar kotak menggunakan hubungan rotatedBox[i][j] = kotak[m - 1 - j][i].
2. Mulakan lelaran dari bahagian bawah kotak dan bagi setiap sel kosong, semak jika terdapat sebarang batu di atasnya tanpa halangan di antaranya.

Penyelesaian:

Kita perlu mengikuti beberapa langkah yang berbeza:

1. Putar kotak: Kami mula-mula memutar matriks 90 darjah mengikut arah jam. Matriks yang diputar akan mempunyai n baris dan m lajur, dengan n ialah bilangan lajur dalam kotak asal dan m ialah bilangan baris.

2. Kesan graviti: Selepas berputar, kita perlu mensimulasikan kesan graviti. Ini bermakna semua batu ('#') harus "jatuh" ke bahagian bawah lajur baharunya, berhenti hanya apabila mereka menghadapi halangan ('*') atau batu lain ('#').

Pendekatan:

1. Putaran: Selepas putaran, elemen pada kedudukan [i][j] dalam matriks asal akan diletakkan pada kedudukan [j][m-1-i] dalam putaran matriks.

2. Simulasi graviti: Kita perlu memproses setiap lajur dari bawah ke atas. Jika ada batu ('#'), ia akan jatuh ke bawah sehingga mencapai halangan atau bahagian bawah. Jika sel itu kosong ('.'), ia boleh memuatkan batu.

Penjelasan langkah demi langkah:

1. Buat matriks baharu untuk kotak yang diputar.
2. Lelaran melalui setiap lajur matriks yang diputar (selepas putaran).
3. Simulasikan graviti untuk setiap lajur dengan bermula dari bawah dan bergerak ke atas. Letakkan batu ('#') sejauh mungkin ke bawah, tinggalkan halangan ('*') di tempatnya.
4. Kembalikan matriks putaran akhir.

Mari laksanakan penyelesaian ini dalam PHP: 1861. Memusingkan Kotak

<?php
function rotateTheBox($box) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$box = [
    ["#", ".", "#"],
];
print_r(rotateTheBox($box));

$box = [
    ["#", ".", "*", "."],
    ["#", "#", "*", "."],
];
print_r(rotateTheBox($box));

$box = [
    ["#", "#", "*", ".", "*", "."],
    ["#", "#", "#", "*", ".", "."],
    ["#", "#", "#", ".", "#", "."],
];
print_r(rotateTheBox($box));
?>




<h3>
  
  
  Penjelasan:
</h3>

<ol>
<li>
<p><strong>Simulasikan Graviti</strong>:</p>

<ul>
<li>Lintas setiap baris dari kanan ke kiri. Gunakan penunjuk (Slot kosong) untuk menjejak di mana batu seterusnya akan jatuh.</li>
<li>Jika batu (#) ditemui, alihkannya keSlot kosong, dan kemudian kurangkan Slot kosong.</li>
<li>Jika halangan (*) ditemui, tetapkan semulaSlot kosong ke kedudukan sejurus sebelum halangan.</li>
</ul>
</li>
<li>
<p><strong>Putar Matriks</strong>:</p>

<ul>
<li>Buat matriks baharu di mana elemen di [i][j] dalam kotak diputar diambil daripada [m - 1 - j][i] kotak asal.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Contoh Output
</h3>

<h4>
  
  
  Input:
</h4>



<pre class="brush:php;toolbar:false">$box = [
    ["#", ".", "#"],
];

Output:

[
    [".",],
    ["#",],
    ["#",],
]

Input:

$box = [
    ["#", ".", "*", "."],
    ["#", "#", "*", "."],
];

Output:

[
    ["#", "."],
    ["#", "#"],
    ["*", "*"],
    [".", "."],
]

Kerumitan Masa

1. Simulasi graviti: O(m x n), sambil kita mengulangi setiap elemen dalam matriks.
2. Putaran: O(m x n), semasa kita mencipta matriks diputar.

Jumlah: O(m x n).

Kerumitan Ruang

• O(m x n) untuk matriks diputar.

Penyelesaian ini cekap dan mematuhi kekangan masalah.

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 Memusingkan Kotak. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!