Chúng ta được cho một ma trận vuông chỉ chứa 0 và 1. 0 đại diện cho nơi trống và 1 có nghĩa là chướng ngại vật. Chúng ta phải tìm số gương có thể đặt tại các ô trống sao cho các gương này có thể truyền ánh sáng từ dưới lên phải. Điều này có thể khi gương đặt tại chỉ số [i,j] và tất cả các ô bên phải trong hàng đó (i) và các ô ở dưới (j) trong cột đó không có chướng ngại vật.
Nếu gương tại A[i][j], thì tất cả A[i+1 đến n][j] và A[i][j+1 đến n] đều trống tức là 0. Như hình dưới đây.
Ví dụ
Đầu vào
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}}
Đầu ra
Số gương: 3
Giải thích − Như hình vẽ. Gương có thể đặt tại các ô:
Arr[1][0] − hàng 1 và cột 0 toàn 0 bên dưới và bên phải.
Arr[2][0] − hàng 2 và cột 0 toàn 0 bên dưới và bên phải.
Arr[4][4] − Ô cuối cùng, là 0 và không có hàng dưới, cột phải.
Phương pháp sử dụng trong chương trình dưới đây
- Mảng Arr[][] biểu diễn ma trận 0 và 1.
- Hàm maximumMirror(int mat[][], int n) nhận ma trận và cạnh n, trả về số gương tối đa có thể đặt như trên.
- Biến flag đánh dấu sự hiện diện chướng ngại vật trong ô dưới hoặc ô phải của arr[i][j].
- Count đại diện cho số gương, khởi tạo 0.
- Duyệt ma trận từ chỉ số 0,0.
- Với mỗi ô nếu trống (có thể đặt gương), kiểm tra ô dưới (k=i+1 đến n-1). Nếu bất kỳ arr[k][j] là chướng ngại vật (giá trị=1) thì thoát vòng while và đặt flag=1. Nếu không, tiếp tục kiểm tra ô bên phải (l=j+1 đến n-1).
- Đặt flag nếu có chướng ngại vật.
- Sau cả hai vòng while nếu flag là 0 thì tăng count vì gương có thể đặt.
- Trả về count là số gương tối đa.
Ví dụ mã nguồn
// C++ program to find how many mirrors can transfer
// light from bottom to right
#include <bits/stdc++.h>
using namespace std;
// Phương thức trả về số gương có thể truyền
// ánh sáng từ dưới lên phải
int maximumMirror(int mat[5][5], int N) {
// đánh dấu tất cả ô bên phải hoặc dưới là 0 - không chướng ngại
int flag = 0;
int count = 0; // số gương
int i, j, k, l;
// với tất cả ô
for (int i = 0; i < N; i++)
for (j = 0; j < N; j++) {
// kiểm tra từ cột tiếp theo và hàng tiếp theo
int k = i + 1;
int l = j + 1;
if (mat[i][j] == 0) { // vị trí cho gương
while (k < N) { // kiểm tra hàng dưới
if (mat[k][j] == 1) { // cột cố định, nếu có chướng ngại vật break
flag = 0;
break;
}
else
flag = 1;
k++;
}
if (flag == 1) { // nếu không chướng ngại vật hàng thì kiểm tra cột bên phải
while (l < N) { // kiểm tra cột bên phải
if (mat[i][l] == 1) { // hàng cố định, nếu chướng ngại vật break
flag = 0;
break;
}
else
flag = 1;
l++;
}
if (flag == 1) { // không chướng ngại vật cho gương mat[i][j]
count++;
}
}
}
}
return count;
}
int main() {
int N = 5;
// ma trận 1 là chướng ngại vật từ ma trận 5x5
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 << "Số gương tối đa truyền ánh sáng từ dưới lên phải: "
<< maximumMirror(mat, N) << endl;
return 0;
}
Kết quả
Số gương tối đa truyền ánh sáng từ dưới lên phải: 3