ในปัญหานี้ เราได้รับเมทริกซ์ไบนารี bin[][] ขนาด nXm ที่ประกอบด้วย 0 และ 1 เท่านั้น งานของเราคือ หาเส้นรอบรูปของรูปทรงที่ประกอบด้วย 1 ในเมทริกซ์ไบนารี
เส้นรอบรูปจะครอบคลุมรูปทรงจากทุกด้าน คือ
สำหรับค่า 1 เดียว เส้นรอบรูปคือ 4
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input
bin[][] = [1, 0] [1, 0]
Output
6
อธิบาย
เซลล์ (0,0) และ (1, 0) เชื่อมต่อกันทำให้เป็นสี่เหลี่ยมผืนผ้าที่มีด้าน 2 และ 1 เส้นรอบรูปคือ 6
วิธีแก้ปัญหา
วิธีแก้ที่ง่ายคือหา 1 ทั้งหมดและส่วนที่มีส่วนร่วมต่อเส้นรอบรูป แล้วบวกทั้งหมดเพื่อหาค่า
ส่วนที่มีส่วนร่วมของ 1 ต่อเส้นรอบรูปในเมทริกซ์คือ ส่วนร่วมสูงสุดคือ 4 เมื่อ 1 เดียวมีส่วนร่วมต่อเส้นรอบรูป
ส่วนร่วมต่ำสุดคือ 0 เมื่อ 1 ถูกล้อมรอบด้วย 1 ทุกด้าน
ดังนั้น สำหรับแต่ละองค์ประกอบของเมทริกซ์ เราต้องตรวจสอบว่ามันเป็น 1 หรือไม่ สำหรับ 1 ทั้งหมด เราจะหาเพื่อนบ้าน และส่วนที่มีส่วนร่วมต่อเส้นรอบรูป แล้วหาเส้นรอบรูปสุดท้าย
โปรแกรมแสดงการทำงานของวิธีแก้
ตัวอย่าง
#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
