ในปัญหานี้ เราได้รับเมทริกซ์ 2 มิติขนาด nXm ซึ่งประกอบด้วย 0 และ 1 เท่านั้น งานของเราคือ หาความยาวของขอบเขตที่ใหญ่ที่สุดในบูลีนเมทริกซ์
คำอธิบายปัญหา: ถ้าเซลล์มี 1 แสดงว่าเป็นเซลล์ที่เติม เราจำเป็นต้องค้นหาความยาวของเซลล์ที่เชื่อมต่อซึ่งเชื่อมต่อกัน ในแนวนอนหรือแนวตั้งหรือแนวทแยงมุม
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: เมทริกซ์[4][5]
{ {0, 1, 1, 0, 1},
{0, 0, 1, 1, 1},
{1, 0, 0, 0, 0},
{1, 0, 1, 0, 1} }
ผลลัพธ์: 6
คำอธิบาย:
จำนวนเซลล์ที่เติมที่เชื่อมต่อคือ 1, 2, 6
แนวทางการแก้ปัญหา -
ในการแก้ปัญหา เราแค่ต้องนับจำนวนรวมของเซลล์ที่เชื่อมต่อของเมทริกซ์
สำหรับสิ่งนี้ เราจะดำเนินการ DFS สำหรับเซลล์ซึ่งจะตรวจสอบเซลล์ที่อยู่ใกล้เคียงทั้งหมดของเซลล์ปัจจุบัน (สำหรับเซลล์หนึ่งเซลล์สามารถมีเซลล์เพื่อนบ้านได้ 8 เซลล์) สำหรับแต่ละเซลล์ เราต้องตรวจสอบว่ามีการเยี่ยมชมเซลล์นั้นหรือไม่โดยการติดตามโดยใช้ hash-map และเมื่อเสร็จสิ้น เราต้องคืนค่าจำนวนเซลล์ที่เข้าชมสูงสุด
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5
int isNotVisited(int M[][COL], int row, int col, bool visited[][COL]) {
return (row >= 0) && (row < ROW) && (col >= 0 ) && (col < COL) && (M[row][col] && !visited[row][col]);
}
void depthFirstSearch(int M[][COL], int row, int col, bool visited[][COL], int& count){
static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
visited[row][col] = true;
for (int k = 0; k < 8; ++k) {
if (isNotVisited(M, row + rowNbr[k], col + colNbr[k], visited)) {
count++;
depthFirstSearch(M, row + rowNbr[k], col + colNbr[k], visited, count);
}
}
}
int findLargestRegionLength(int M[][COL]) {
bool isvisited[ROW][COL];
memset(isvisited, 0, sizeof(isvisited));
int maxCount = -1;
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
if (M[i][j] && !isvisited[i][j]) {
int count = 1;
depthFirstSearch(M, i, j, isvisited, count);
maxCount = max(maxCount, count);
}
}
}
return maxCount;
}
int main(){
int M[][COL] = { {0, 1, 1, 0, 1},
{0, 0, 1, 1, 1},
{1, 0, 0, 0, 0},
{1, 0, 1, 0, 1} };
cout<<"The length of largest region is "<<findLargestRegionLength(M);
return 0;
} ผลลัพธ์
The length of largest region is 6
