檢查給定的二進位矩陣中是否存在連續的T個0的區塊

簡介

二元矩陣廣泛應用於電腦科學和各個領域，以有效地表示資料或解決複雜問題。在某些情況下，識別給定的二進位矩陣是否包含連續的零塊變得非常重要。在本文中，我們將使用 C 程式碼探索一種優雅的解決方案，該解決方案允許我們檢測給定二進位矩陣中是否存在 T 個連續的零區塊。這種方法既直觀又高效，適合實際實施。

檢查是否有T個連續的0塊

給定一個維度為 N x M 和整數 T 的二維二進位矩陣，我們需要確定矩陣中是否存在 T 個連續的零塊（其中「連續」意味著水平或垂直相鄰）。為了實現這一目標，讓我們使用邏輯和演算法方法逐步分解這個過程。

輸入驗證

在深入探索二進位矩陣中的模式之前，驗證使用者輸入的適當尺寸和相關特徵非常重要。我們必須確保 T 在可接受的範圍內，以提供可行的結果同時保持計算效率

遍歷行和列

為了有效率地決定連續的零塊，我們必須分別分析行和列。例如，從第一行（最頂部）開始，我們將按列遍歷所有元素，直到第N行（最底部）。同時遍歷列有助於自然地捕捉水平和垂直序列，而不會錯過任何潛在的組合

偵測連續區塊

當我們遍歷每一行的每一列時，辨識連續的零構成了偵測連續零塊時的基石。

一個二進位矩陣是一個僅由0和1組成的數組，其中每個元素分別表示「關閉」或「開啟」狀態。透過分析這兩種狀態，我們可以識別出可能提供關聯性或相鄰元素之間獨特排列的獨特模式。

範例

二進位矩陣被視為，

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

我們需要找出矩陣中連續的零塊的數量。 T的值為3。

我們可以使用深度優先搜尋（DFS）來找出矩陣中連續的零塊。我們先按行和列遍歷矩陣。如果我們遇到之前沒有訪問過的零元素，我們會將其壓入堆疊並從該元素開始 DFS。

在 DFS 流程中，我們檢查目前儲存格的四個相鄰儲存格（上、下、左、右）。如果這些單元中的任何一個為零並且之前未被訪問過，我們將它們壓入堆疊並從該單元繼續 DFS。

我們也會追蹤迄今為止遇到的連續零塊的數量。如果這個計數大於或等於T，我們回傳「是」。否則，我們繼續DFS直到所有單元格都被訪問

在這種情況下，我們從儲存格（0,1）開始進行深度優先搜尋（DFS）。我們在（0,2）和（0,3）處遇到了另外兩個零元素，並將它們添加到我們目前的路徑中。然後我們回溯到單元格（0,1）並檢查其相鄰單元格。我們在（1,1）處又遇到了另一個零元素，並將其添加到我們目前的路徑中。然後我們再次回溯到單元格（0,1）並檢查其相鄰單元格。我們沒有遇到任何尚未訪問過的零元素

然後我們從儲存格 (3,1) 開始 DFS。我們在 (3,2) 和 (3,3) 處遇到了另外兩個零元素，並將它們添加到我們目前的路徑中。然後我們回溯到單元格 (3,1) 並檢查其相鄰單元格。我們不會再遇到之前未造訪過的零元素。

我們現在在矩陣中找到了三個連續的零塊。由於這個計數大於或等於T=3，所以輸出為“是”

方法1：C 程式碼檢查是否有T個連續的0塊

為了實現我們的目標，我們可以在二進位矩陣上利用圖遍歷技術，同時追蹤已存取的單元格。我們將使用深度優先搜尋（DFS）演算法結合回溯原則。

演算法

步驟1：初始化必要的變量，如定義常數`N` 和`M` 表示輸入二進位矩陣的大小，聲明輔助布林數組'visited' 和'inCurrentPath'，每個數組的大小為N x M，並將兩個陣列中的所有元素初始設為false

步驟2：實作DFS函數並包含main函數

第 3 步：根據輸入的二進位矩陣，輸出列印為 yes 或 no。

範例

#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;
}

輸出

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

結論

透過利用所提出的 C 程式碼，該程式碼採用涉及深度優先搜尋 (DFS) 的圖遍歷技術，我們可以方便地確定二進位矩陣中是否存在給定數量 (T) 的連續零區塊。該解決方案提供了一種有效的方法來解決與二進制矩陣相關的問題，並允許研究人員和開發人員有效地創建強大的演算法。

以上是檢查給定的二進位矩陣中是否存在連續的T個0的區塊的詳細內容。更多資訊請關注PHP中文網其他相關文章！