Permainan Grid

2017. Permainan Grid

Kesukaran: Sederhana

Topik: Tatasusunan, Matriks, Jumlah Awalan

Anda diberi 0-diindeks grid tatasusunan 2D bersaiz 2 x n, dengan grid[r][c] mewakili bilangan titik pada kedudukan (r, c) pada matriks. Dua robot sedang bermain permainan pada matriks ini.

Kedua-dua robot pada mulanya bermula pada (0, 0) dan mahu mencapai (1, n-1). Setiap robot hanya boleh bergerak ke kanan ((r, c) ke (r, c 1)) atau bawah ((r, c) ke (r 1, c)).

Pada permulaan permainan, robot pertama bergerak dari (0, 0) ke (1, n-1), mengumpul semua mata daripada sel di laluannya. Untuk semua sel (r, c) yang dilalui pada laluan, grid[r][c] ditetapkan kepada 0. Kemudian, robot saat bergerak dari (0, 0) ke (1, n-1 ), mengumpul mata pada laluannya. Ambil perhatian bahawa laluan mereka mungkin bersilang antara satu sama lain.

Robot pertama mahu meminimumkan bilangan mata yang dikumpul oleh robot kedua. Sebaliknya, robot kedua mahu memaksimumkan bilangan mata yang dikumpulnya. Jika kedua-dua robot bermain secara optimum, kembalikan bilangan mata yang dikumpul oleh saat robot.

Contoh 1:

• Input: grid = [[2,5,4],[1,5,1]]
• Output: 4
• Penjelasan: Laluan optimum yang diambil oleh robot pertama ditunjukkan dalam warna merah, dan laluan optimum yang diambil oleh robot kedua ditunjukkan dengan warna biru.
  • Sel yang dilawati oleh robot pertama ditetapkan kepada 0.
  • Robot kedua akan mengumpul 0 0 4 0 = 4 mata.

Contoh 2:

• Input: grid = [[3,3,1],[8,5,2]]
• Output: 4
• Penjelasan: Laluan optimum yang diambil oleh robot pertama ditunjukkan dalam warna merah, dan laluan optimum yang diambil oleh robot kedua ditunjukkan dengan warna biru.
  • Sel yang dilawati oleh robot pertama ditetapkan kepada 0.
  • Robot kedua akan mengumpul 0 3 1 0 = 4 mata.

Contoh 3:

• Input: grid = [[1,3,1,15],[1,3,3,1]]
• Output: 7
• Penjelasan: Laluan optimum yang diambil oleh robot pertama ditunjukkan dalam warna merah, dan laluan optimum yang diambil oleh robot kedua ditunjukkan dengan warna biru.
  • Sel yang dilawati oleh robot pertama ditetapkan kepada 0.
  • Robot kedua akan mengumpul 0 1 3 3 0 = 7 mata.

Kekangan:

• grid.length == 2
• n == grid[r].panjang
• 1 4
• 1 5

Petunjuk:

1. Terdapat n pilihan apabila robot pertama bergerak ke baris kedua.
2. Bolehkah kita menggunakan jumlah awalan untuk membantu menyelesaikan masalah ini?

Penyelesaian:

Kami akan menggunakan pendekatan berikut:

1. Pengiraan Jumlah Awalan: Kami akan mengira jumlah awalan untuk kedua-dua baris grid untuk mengira dengan cekap jumlah mata bagi mana-mana subray.

2. Mensimulasikan Pergerakan Optimum:

   • Robot pertama menentukan laluannya untuk meminimumkan mata yang tinggal untuk robot kedua.
   • Pada setiap peralihan lajur, robot pertama boleh memilih untuk bergerak ke bawah, membahagikan grid kepada dua segmen:
     • Titik baki atas: Mata di baris atas selepas lajur peralihan.
     • Tinggal baki bawah: Mata di baris bawah sebelum lajur peralihan.

3. Meminimumkan Mata Maksimum untuk Robot Kedua:

   • Pada setiap peralihan, hitung mata maksimum yang boleh dikumpulkan oleh robot kedua selepas laluan robot pertama.
   • Jejak minimum maksimum ini merentas semua peralihan.

Mari kita laksanakan penyelesaian ini dalam PHP: 2017. Permainan Grid

<?php function gridGame($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$grid1 = [[2, 5, 4], [1, 5, 1]];
$grid2 = [[3, 3, 1], [8, 5, 2]];
$grid3 = [[1, 3, 1, 15], [1, 3, 3, 1]];

echo gridGame($grid1) . "\n"; // Output: 4
echo gridGame($grid2) . "\n"; // Output: 4
echo gridGame($grid3) . "\n"; // Output: 7
?>

Penjelasan:

1. Pengiraan Jumlah Awalan:

   • prefixTop dan prefixBottom menyimpan jumlah terkumpul untuk baris atas dan bawah, masing-masing.
   • Ini membolehkan pengiraan jumlah julat yang cekap.

2. Mensimulasikan Laluan Robot Pertama:

   • Di setiap lajur i, robot pertama boleh memutuskan untuk bergerak ke bawah selepas lajur i.
   • Ini membahagikan grid kepada dua kawasan:
     • Baris atas selepas lajur i (mata terkumpul: awalanAtas[n] - awalanAtas[i 1]).
     • Baris bawah sebelum lajur i (titik terkumpul: awalanBawah[i]).

3. Mata Optimum Robot Kedua:

   • Robot kedua akan mengambil maksimum dua kawasan yang tinggal.
   • Kami menjejaki minimum maksimum ini untuk semua peralihan yang mungkin.

4. Kerumitan:

   • Kerumitan Masa: O(n), sambil kita mengira jumlah awalan dan gelung melalui grid sekali.
   • Kerumitan Angkasa: O(n), disebabkan tatasusunan jumlah awalan.

Contoh Panduan

Input: grid = [[2, 5, 4], [1, 5, 1]]

• Jumlah Awalan:
  • prefixTop = [0, 2, 7, 11]
  • prefixBottom = [0, 1, 6, 7]
• Mata Peralihan:
  • i = 0: Baki Atas = 11 - 7 = 9, Baki Bawah = 0 → Robot Kedua = 9.
  • i = 1: Baki Atas = 11 - 11 = 4, Baki Bawah = 1 → Robot Kedua = 4.
  • i = 2: Baki Atas = 0, Baki Bawah = 6 → Robot Kedua = 6.
• Mata Minimum untuk Robot Kedua: min(9, 4, 6) = 4.

Ini sepadan dengan output yang dijangkakan.

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