0과 1만 포함하는 정사각형 행렬이 제공됩니다. 0은 빈 공간을 나타내고 1은 장애물을 의미합니다. 우리는 이러한 거울들이 빛을 아래에서 오른쪽으로 전달할 수 있도록 하기 위해 세포를 배치할 수 있는 다수의 거울을 찾아야 합니다. 이것은 미러가 인덱스 [i,j]에 배치되고 해당 특정 행(i)의 오른쪽에 있는 모든 셀과 해당 특정 열의 맨 아래(j)에 있는 셀에 장애물이 없을 때 가능합니다.
미러가 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이고 아래에 행이 없고 오른쪽에 열이 있습니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
Array Arr[][]은 0과 1의 행렬을 나타내는 데 사용됩니다.
-
maximumMirror(int mat[][], int n) 함수는 행렬을 취하고 측면 n을 입력으로 하고 위와 같이 배치할 수 있는 최대 미러 수를 반환합니다.
-
변수 플래그는 arr [i] [j] 아래 셀이나 오른쪽 셀에 장애물이 있음을 표시하는 데 사용됩니다.
-
Count는 미러 수를 나타내는 데 사용되며 처음에는 0입니다.
-
인덱스 0,0에서 행렬을 트래버스합니다.
-
각 셀이 비어 있는 경우(거울을 배치할 수 있음) 아래의 셀( k=i+1 ~ n-1)을 확인합니다. arr[k][j]가 장애물(값=1)이면 중단하는 동안 루프를 만들고 플래그를 1로 표시합니다. 그렇지 않으면 오른쪽에 있는 셀을 계속 확인합니다( l=j+1 ~ n-1 ).
-
장애물이 있는 경우 플래그를 설정합니다.
-
두 while 루프 후 플래그가 0이면 미러로 카운트를 증가시킬 수 있습니다.
-
카운트를 아니오로 반환합니다. 최대 미러 수입니다.
예
// C++ program to find how many mirrors can transfer
// light from bottom to right
#include <bits/stdc++.h>
using namespace std;
// method returns number of mirror which can transfer
// light from bottom to right
int maximumMirror(int mat[5][5], int N){
// to mark that all cells in the right or bottom are 0---no obstacle
int flag=0;
int count=0; //count of mirrors
int i,j,k,l;
//for all cells
for (int i=0; i<N; i++)
for(j=0;j<N;j++){
//check from next column and next row
int k=i+1;
int l=j+1;
if(mat[i][j]==0) //position for mirror{
while(k<N) //check for rows below{
if(mat[k][j]==1) //keeping column fixed, if there is obstacle break{
flag=0; break; }
else
flag=1;
k++;
}
if(flag==1) //if no obstacle in rows then check columns in right
while(l<N) //checking for columns in right{
if(mat[i][l]==1) //keep row fixed, if obstacle break{
flag=0; break;
}
else
flag=1;
l++;
}
if(flag==1) //there is no obstacle for mirror mat[i][j]
count++;
}
}
return count;
}
int main(){
int N = 5;
//matrix where 1 represents obstacle form 5X5 matrix
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