Semak sama ada terdapat blok T berturut-turut 0 dalam matriks binari yang diberikan

Pengenalan

Matriks binari digunakan secara meluas dalam sains komputer dan pelbagai bidang untuk mewakili data dengan berkesan atau menyelesaikan masalah yang kompleks. Dalam sesetengah kes, menjadi penting untuk mengenal pasti sama ada matriks binari tertentu mengandungi blok sifar berturut-turut. Dalam artikel ini, kami akan meneroka penyelesaian elegan menggunakan kod C++ yang membolehkan kami mengesan kehadiran blok sifar T berturut-turut dalam matriks binari tertentu. Pendekatan ini adalah intuitif dan cekap, menjadikannya sesuai untuk pelaksanaan praktikal.

Periksa sama ada terdapat T 0 blok berturut-turut

Memandangkan matriks perduaan dua dimensi berdimensi N x M dan integer T, kita perlu menentukan sama ada terdapat T blok sifar berturut-turut dalam matriks (di mana "bersambung" bermaksud bersebelahan mendatar atau menegak). Untuk mencapai matlamat ini, mari kita pecahkan proses langkah demi langkah menggunakan kaedah logik dan algoritma.

Pengesahan input

Sebelum mendalami penerokaan corak dalam matriks binari, adalah penting untuk mengesahkan dimensi yang sesuai dan ciri-ciri yang relevan bagi input pengguna. Kita mesti memastikan bahawa T berada dalam julat yang boleh diterima untuk memberikan hasil yang boleh dilaksanakan sambil mengekalkan kecekapan pengiraan

Melintasi baris dan lajur

Untuk menentukan blok sifar berturut-turut dengan cekap, kita mesti menganalisis baris dan lajur secara berasingan. Sebagai contoh, bermula dari baris pertama (paling atas), kami akan mengulangi semua elemen mengikut lajur hingga baris N (paling bawah). Melintasi lajur secara serentak membantu menangkap jujukan mendatar dan menegak secara semula jadi tanpa kehilangan sebarang kombinasi yang berpotensi

Kesan blok berturut-turut

Mengenal pasti sifar berturut-turut membentuk asas pengesanan blok sifar berturut-turut semasa kami melelakan setiap lajur setiap baris.

Matriks binari ialah tatasusunan yang hanya terdiri daripada 0s dan 1s, di mana setiap elemen mewakili keadaan "mati" atau "hidup". Dengan menganalisis kedua-dua keadaan ini, kita boleh mengenal pasti corak unik yang mungkin memberikan korelasi atau susunan unik antara elemen bersebelahan.

Contoh

Matriks binari dianggap sebagai,

1 0 0 0 1
1 0 0 0 1
1 1 1 1 1
1 0 0 0 1

Kita perlu mencari bilangan blok sifar berturut-turut dalam matriks. Nilai T ialah 3.

Kita boleh menggunakan Depth First Search (DFS) untuk mencari blok sifar berturut-turut dalam matriks. Kami mula-mula mengulangi matriks mengikut baris dan lajur. Jika kami menemui elemen sifar yang belum pernah diakses sebelum ini, kami menolaknya ke dalam tindanan dan memulakan DFS daripada elemen itu.

Semasa proses DFS, kami menyemak empat sel jiran (atas, bawah, kiri, kanan) sel semasa. Jika mana-mana sel ini adalah sifar dan belum pernah diakses sebelum ini, kami menolaknya ke dalam tindanan dan meneruskan DFS dari sel itu.

Kami juga menjejaki bilangan blok sifar berturut-turut yang ditemui setakat ini. Jika kiraan ini lebih besar daripada atau sama dengan T, kami kembalikan "ya". Jika tidak, kami meneruskan DFS sehingga semua sel telah dilawati

Dalam kes ini, kami melakukan Carian Pertama Kedalaman (DFS) bermula dari sel (0,1). Kami menemui dua lagi elemen sifar pada (0,2) dan (0,3) dan menambahnya pada laluan semasa kami. Kami kemudian berundur ke sel (0,1) dan menyemak sel jirannya. Kami menemui satu lagi elemen sifar pada (1,1) dan menambahnya pada laluan semasa kami. Kemudian kami kembali ke sel (0,1) sekali lagi dan periksa sel jirannya. Kami belum menemui sebarang elemen sifar yang belum dilawati lagi

Kemudian kita mulakan DFS dari sel (3,1). Kami menemui dua lagi elemen sifar pada (3,2) dan (3,3) dan menambahnya pada laluan semasa kami. Kami kemudian berundur ke sel (3,1) dan menyemak sel jirannya. Kami tidak akan menemui unsur sifar yang belum pernah kami lawati sebelum ini.

Kami kini menemui tiga blok sifar berturut-turut dalam matriks. Oleh kerana kiraan ini lebih besar daripada atau sama dengan T=3, output ialah "Ya"

Kaedah 1: Kod C++ menyemak sama ada terdapat T 0 blok berturut-turut

Untuk mencapai matlamat kami, kami boleh menggunakan teknik traversal graf pada matriks binari sambil menjejaki sel yang dilawati. Kami akan menggunakan algoritma Depth First Search (DFS) digabungkan dengan prinsip backtracking.

Algoritma

Langkah 1: Mulakan pembolehubah yang diperlukan, seperti menentukan pemalar `N` dan `M` untuk mewakili saiz matriks binari input, dan mengisytiharkan tatasusunan Boolean tambahan 'dilawati' dan 'inCurrentPath', dengan saiz setiap tatasusunan menjadi N x M, dan pada mulanya menetapkan semua elemen dalam kedua-dua tatasusunan kepada palsu

Langkah 2: Laksanakan fungsi DFS dan sertakan fungsi utama

Langkah 3: Bergantung pada matriks binari input, output dicetak sebagai ya atau tidak.

Contoh

#include<iostream>
#include<stack>
#include<bitset>

#define N 100
#define M 100

struct Node {
   int i;
   int j;
};

bool DFS(bool matrix[], int rows, int cols, int T)
{
   if(matrix == nullptr || rows <= 0 || cols <= 0 || T <= 0) // check for invalid input
      return false;

   std::bitset<N*M> visited; // declare bitset to mark visited cells
   std::bitset<N*M> inCurrentPath; // declare bitset to mark cells in current path
   std::stack<Node> s; // declare stack to store nodes for DFS

   for(int i=0;i<rows;++i){
      for(int j=0;j<cols;++j){

         if(matrix[i*cols+j] == 0 && !visited[i*cols+j]){

            s.push({i,j});
            int count = 0; // initialize count to zero for each new search

            while(!s.empty()){

               Node node = s.top();
               s.pop();

               if(node.i < 0 || node.i >= rows || node.j < 0 || node.j >= cols || visited[node.i*cols+node.j])
                  continue;

               visited[node.i*cols+node.j] = true;

               if(matrix[node.i*cols+node.j] == 0 && !inCurrentPath[node.i*cols+node.j]){
                  inCurrentPath[node.i*cols+node.j] = true;
                  count++;
               }

               if(count >= T){
                  std::cout << "Yes, the path is: "; // print yes and the path
                  for(int k=0;k<N*M;++k){
                     if(inCurrentPath[k]){
                        std::cout << "(" << k/cols << "," << k%cols << ") "; // print the coordinates of the cells in the path
                     }
                  }
                  std::cout << "\n";
                  return true;
               }

               s.push({node.i+1,node.j});
               s.push({node.i-1,node.j});
               s.push({node.i,node.j+1});
               s.push({node.i,node.j-1});
            }

            inCurrentPath.reset(); // reset the path after each search
         }
      }
   }

   std::cout << "No\n"; // print no if no path is found
   return false;
}

int main()
{
   bool matrix[N*M] = {1,1,0,0,1,
                  1,0,0,0,1,
                  1,1,1,1,1,
                  1,1,0,0,1,
                  }; // Binary matrix

   int T = 3; // Number of continuous blocks to find

   DFS(matrix, N, M, T); // call DFS function

   return 0;
}

Output

Yes, the path is: (0,2) (1,0) (1,1)

Kesimpulan

Dengan memanfaatkan kod C++ yang dicadangkan, yang menggunakan teknik traversal graf yang melibatkan carian pertama mendalam (DFS), kita boleh menentukan dengan mudah sama ada nombor tertentu (T) blok sifar berturut-turut hadir dalam matriks binari. Penyelesaian ini menyediakan cara yang cekap untuk menyelesaikan masalah yang berkaitan dengan matriks binari dan membolehkan penyelidik dan pembangun mencipta algoritma yang berkuasa dengan cekap.

Atas ialah kandungan terperinci Semak sama ada terdapat blok T berturut-turut 0 dalam matriks binari yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!