ในปัญหานี้ เราได้รับไบนารีเมทริกซ์ bin[][] ขนาด nXm ซึ่งประกอบด้วย 0 และ 1 เท่านั้น งานของเราคือค้นหาขอบเขตของรูปร่างที่เกิดขึ้นจาก 1s ในเมทริกซ์ไบนารี
เส้นรอบวงที่ถ่ายจะครอบคลุมร่างจากทุกด้านเช่น
สำหรับ 1 ค่าเดียว เส้นรอบรูปคือ 4
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
bin[][] = [1, 0] [1, 0]
ผลลัพธ์
6
คำอธิบาย
เซลล์ (0,0) และ (1, 0) เชื่อมต่อกันโดยให้สี่เหลี่ยมด้านที่ 2 และ 1 เส้นรอบรูปคือ 6
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ ก็คือการค้นหาทั้งหมดหนึ่งข้อและการมีส่วนร่วมของพวกมันในขอบเขต แล้วบวกทั้งหมดเพื่อค้นหาค่า
การมีส่วนร่วมของ 1 ต่อปริมณฑลในเมทริกซ์คือ การมีส่วนร่วมสูงสุดคือ 4 เมื่อ 1 เพียงอย่างเดียวมีส่วนในปริมณฑล
การบริจาคขั้นต่ำคือ 0 เมื่อ 1 ถูกล้อมรอบด้วย 1 ทุกด้าน
ดังนั้น สำหรับแต่ละองค์ประกอบของเมทริกซ์ เราต้องตรวจสอบว่ามันเป็น 1 หรือไม่ สำหรับ all1 เราจะหาเพื่อนบ้าน จากนั้นจึงมีส่วนร่วมในปริมณฑลและสุดท้ายคือปริมณฑล
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<iostream>
using namespace std;
#define R 3
#define C 5
int contibutionToPerimeter(int mat[][C], int i, int j) {
int neighbours = 0;
if (i > 0 && mat[i - 1][j])
neighbours++;
if (j > 0 && mat[i][j - 1])
neighbours++;
if (i < R-1 && mat[i + 1][j])
neighbours++;
if (j < C-1 && mat[i][j + 1])
neighbours++;
return (4 - neighbours);
}
int calcPerimeter(int mat[R][C]){
int perimeter = 0;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
if (mat[i][j] == 1)
perimeter += contibutionToPerimeter(mat, i ,j);
return perimeter;
}
int main() {
int mat[R][C] = { {0, 1, 0, 0, 0},
{1, 1, 1, 1, 0},
{1, 1, 0, 1, 1} };
cout<<"The perimeter of shapes from formed with 1s is "<<calcPerimeter(mat);
return 0;
} ผลลัพธ์
The perimeter of shapes from formed with 1s is 18
