資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究檢查給定二進位制矩陣中是否存在 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 函式幷包含主函式
步驟 3：根據輸入的二進位制矩陣，輸出列印為是或否。
示例
#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)
結論
透過利用提供的使用深度優先搜尋 (DFS) 的圖遍歷技術的 C++ 程式碼，我們可以方便地確定二進位制矩陣中是否存在給定數量 (T) 的連續零塊。此解決方案提供了一種解決與二進位制矩陣相關的相關問題的有效方法，並允許研究人員和開發人員有效地建立強大的演算法。
102 次瀏覽
