เราได้รับเมทริกซ์สี่เหลี่ยมจัตุรัสที่มีแค่ 0 และ 1 โดย 0 = ว่าง, 1 = อุปสรรค ต้องหาจำนวนกระจกที่วางในเซลล์ว่างได้ ซึ่งกระจกสามารถส่งแสงจากล่าง (bottom) ไปขวา (right) ได้ กรณีนี้เป็นไปได้เมื่อ วางกระจกที่ [i,j] และเซลล์ด้านขวาในแถว i และเซลล์ด้านล่างในคอลัมน์ j ไม่มีอุปสรรค (เป็น 0 ทุกตัว)
หากกระจกอยู่ที่ A[i][j] แล้ว A[i+1..n][j] และ A[i][j+1..n] ต้องเป็น 0 ทุกตัว
อินพุต
Arr[][] = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,1,1,0,1},{1,1,1,0,1}}
เอาต์พุต
No. of mirrors: 3
คำอธิบาย − กระจกวางได้ที่:
Arr[1][0] − แถว 1 และคอลัมน์ 0 เป็น 0 ทั้งหมดด้านล่างและขวา
Arr[2][0] − แถว 2 และคอลัมน์ 0 เป็น 0 ทั้งหมดด้านล่างและขวา
Arr[4][4] − เซลล์สุดท้าย เป็น 0 และไม่มีแถวด้านล่าง/คอลัมน์ขวา
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- Arr[][] แทนเมทริกซ์ 0 และ 1
- ฟังก์ชัน maximumMirror(int mat[][], int n) คืนค่าจำนวนกระจกสูงสุด
- flag หมายถึงมีอุปสรรคในเซลล์ด้านล่างหรือขวา
- count นับกระจก เริ่มต้น 0
- ลูปผ่านเมทริกซ์จาก 0,0
- สำหรับเซลล์ว่าง (mat[i][j]==0) ตรวจสอบเซลล์ด้านล่าง (k=i+1..n-1) หากเจอ 1 break flag=0 มิฉะนั้น flag=1
- ถ้า flag=1 ตรวจสอบเซลล์ด้านขวา (l=j+1..n-1) เหมือนกัน
- ถ้า flag=1 หลังทั้งสองลูป เพิ่ม count
- คืนค่า count
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int maximumMirror(int mat[5][5], int N) {
int flag = 0;
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
int k = i + 1, l = j + 1;
if (mat[i][j] == 0) {
while (k < N) {
if (mat[k][j] == 1) { flag = 0; break; }
else flag = 1;
k++;
}
if (flag == 1)
while (l < N) {
if (mat[i][l] == 1) { flag = 0; break; }
else flag = 1;
l++;
}
if (flag == 1) count++;
}
}
return count;
}
int main() {
int N = 5;
int mat[5][5] = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,1,1,0,1},{1,1,1,0,1}};
cout << "Maximum mirrors which can transfer light from bottom to right: "
<< maximumMirror(mat, N) << endl;
return 0;
}
ผลลัพธ์
Maximum mirrors which can transfer light from bottom to right: 3
