Terjemah titik keluar dalam matriks binari menggunakan C++

Matriks binari merujuk, dalam istilah pengaturcaraan komputer, kepada grid baris dan lajur yang terdiri daripada 0s dan 1s. Satu cabaran pengekodan yang dihadapi dalam temu bual pengaturcaraan dan pertandingan ialah menentukan titik keluar dalam matriks binari. Dalam artikel ini, kami akan menerangkan cara yang berbeza untuk menyelesaikan masalah ini menggunakan C++.

tatabahasa

Sebelum mendalami algoritma, kami mungkin mendapati berfaedah untuk membiasakan diri dengan sintaks yang kerap muncul dalam contoh kod yang akan kami tunjukkan.

`pair<int, int> findExitPoint(const vector<vector<int>>& matrix)`.

Algoritma

Sekarang, mari kita gariskan algoritma langkah demi langkah untuk mencari titik keluar dalam matriks binari -

• Mulakan kedudukan sel semasa kepada (0, 0).

• Traverse matriks bermula dari sel semasa.

• Jika sel semasa ialah 1, beralih ke sel seterusnya mengikut keutamaan - kanan, bawah, kiri, atas.

• Jika sel semasa ialah 0, keluar dari gelung dan kembalikan kedudukan sel semasa sebagai titik keluar.

• Ulang langkah 3 dan 4 sehingga titik keluar ditemui atau semua sel telah dilawati.

kaedah satu

Cara pertama yang kami cadangkan ialah dengan melaksanakan gelung sementara dan pernyataan bersyarat untuk melaksanakan algoritma. Berikut ialah contoh yang menunjukkan rupa pelaksanaan ini -

Contoh

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> findExitPoint(const vector<vector<int>>& matrix) {
   int rows = matrix.size();
   int cols = matrix[0].size();
   int x = 0, y = 0;  // Starting cell position

   while (x >= 0 && x < rows && y >= 0 && y < cols) {
      if (matrix[x][y] == 1) {
         // Move right
         if (y + 1 < cols && matrix[x][y + 1] == 1)
            y++;
         // Move down
         else if (x + 1 < rows && matrix[x + 1][y] == 1)
            x++;
         // Move left
         else if (y - 1 >= 0 && matrix[x][y - 1] == 1)
            y--;
         // Move up
         else if (x - 1 >= 0 && matrix[x - 1][y] == 1)
            x--;
      } else {
         break;  // Exit loop when encountering a 0
      }
   }

   return make_pair(x, y);
}

int main() {
   // Matrix initialization
   vector<vector<int>> matrix = {
      {1, 0, 0, 1},
      {1, 1, 0, 1},
      {0, 1, 1, 1},
      {0, 0, 0, 1}
   };

   // Finding the exit point
   pair<int, int> exitPoint = findExitPoint(matrix);

   // Printing the exit point coordinates
   cout << "Exit Point: (" << exitPoint.first << ", " << exitPoint.second << ")" << endl;

   return 0;
}

Output

Exit Point: (3, 3)

Kaedah 2

Untuk mengendalikan pergerakan sel, kaedah kedua kami menggunakan gelung do while digabungkan dengan pernyataan suis. Sebagai rujukan, berikut ialah contoh yang menunjukkan rupa pelaksanaan sedemikian −

Contoh

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> findExitPoint(const vector<vector<int>>& matrix) {
   int rows = matrix.size();
   int cols = matrix[0].size();
   int x = 0, y = 0;  // Starting cell position

   do {
      switch (matrix[x][y]) {
         case 1:  // Move based on the priority order
            if (y + 1 < cols && matrix[x][y + 1] == 1) {
               y++;  // Move right
            } else if (x + 1 < rows && matrix[x + 1][y] == 1) {
               x++;  // Move down
            } else if (y - 1 >= 0 && matrix[x][y - 1] == 1) {
               y--;  // Move left
            } else if (x - 1 >= 0 && matrix[x - 1][y] == 1) {
               x--;  // Move up
            }
            break;
   
            default:  // Exit loop when encountering a 0
         break;
      }
   } while (x >= 0 && x < rows && y >= 0 && y < cols);

   return make_pair(x, y);
}

int main() {
   // Matrix initialization
   vector<vector<int>> matrix = {
      {1, 0, 0, 1},
      {1, 1, 0, 1},
      {0, 1, 1, 1},
      {0, 0, 0, 1}
   };

   // Finding the exit point
   pair<int, int> exitPoint = findExitPoint(matrix);
   
   // Printing the exit point coordinates
   cout << "Exit Point: (" << exitPoint.first << ", " << exitPoint.second << ")" << endl;

   return 0;
}

Output

Exit Point: (3, 3)

Penjelasan

Explain

Fungsi `findExitPoint` direka dalam kod yang disediakan. Tujuannya adalah untuk menerima matriks binari sebagai input dan output sepasang integer yang sepadan dengan koordinat titik keluar. Fungsi ini mengikut algoritma yang diterangkan untuk melintasi matriks dan mencari titik keluar.

Untuk menjejaki kedudukan sel semasa kami semasa merentasi matriks menggunakan kedua-dua teknik pelaksanaan, kami menggunakan pembolehubah `x` dan `y`. Kami kemudian menggunakan gelung untuk menggerakkan matriks mengikut susunan keutamaan: kanan, bawah, kiri dan atas.

Menggunakan gelung sementara, kami menyemak nilai setiap sel dan menggunakan pernyataan if-else. Dengan mengandaikan sel semasa ialah 1, kita beralih ke sel seterusnya dalam arah yang ditentukan. Jika sel semasa ialah 0, kita keluar dari gelung dan mengembalikan kedudukan sel semasa sebagai titik keluar.

Kaedah 2 menggunakan gelung do-while dan pernyataan suis untuk mengendalikan pergerakan sel. Untuk menjadikan proses navigasi cekap, kami menggunakan laluan pelaksanaan berasaskan keadaan yang secara khusus menyasarkan pergerakan ke arah yang sepadan dengan setiap nilai sel semasa yang diberikan. Pada asasnya, apabila sel semasa dengan nilai 1 diproses, ia dilaraskan dengan cepat untuk menampung sebarang pengubahsuaian yang diperlukan untuk nilai koordinat x dan y kami. Dengan mengandaikan bahawa sel semasa ialah 0, kita keluar dari gelung.

Dalam fungsi `utama`, kami memulakan matriks binari dan memanggil fungsi `findExitPoint` untuk mendapatkan koordinat titik keluar. Akhir sekali, kami menggunakan `cout` untuk mencetak koordinat titik keluar.

KESIMPULAN

Tugas pengaturcaraan yang sering dihadapi ialah mencari titik keluar dalam matriks binari, dan tugas ini mencadangkan pelbagai laluan penyelesaian. Kami menyelami dua kaedah berbeza, dilaksanakan dalam kod C++, untuk mengatasi halangan ini dalam artikel ini. Aplikasi yang berjaya bagi algoritma ini boleh menentukan kedudukan akhir matriks binari atau menunjuk ke kedudukan akhir dengan cekap. Ingat untuk memilih strategi yang sepadan dengan pilihan gaya pengekodan dan matlamat akhir yang anda inginkan.

Atas ialah kandungan terperinci Terjemah titik keluar dalam matriks binari menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!