아래에서 오른쪽으로 빛을 전달할 수 있는 최대 거울

각 셀이 공백이나 장애물을 나타내는 정사각형 행렬이 제공됩니다. 빈 위치에 거울을 배치할 수 있습니다. 모든 거울은 45도 각도로 배치됩니다. 즉, 경로에 장애물이 없으면 빛을 아래에서 오른쪽으로 전달할 수 있습니다.

이 질문에서 우리는 아래에서 오른쪽으로 빛을 전달할 수 있는 정사각형 매트릭스에 이러한 거울을 몇 개 배치할 수 있는지 계산해야 합니다.

예:

Output for above example is 2. In above diagram mirror at (3 1) and (5 5) are able to send light from bottom to right so total possible mirror count is 2.

우리는 매트릭스에서 그러한 거울의 위치를 확인함으로써 이 문제를 해결할 수 있습니다. 빛을 아래에서 오른쪽으로 전달할 수 있는 거울은 경로에 장애물이 없을 것입니다.
인덱스(i j)에 미러가 있으면
모든 k i에 대한 인덱스(k j)에는 장애물이 없습니다.< k <= N
모든 k j에 대해 인덱스(i k)에는 장애물이 없습니다.< k <= N
위의 두 방정식을 염두에 두고 주어진 행렬의 한 반복에서 모든 행에서 가장 오른쪽 장애물을 찾을 수 있으며, 주어진 행렬의 또 다른 반복에서 모든 열에서 가장 아래쪽 장애물을 찾을 수 있습니다. 이러한 인덱스를 별도의 배열에 저장한 후 각 인덱스에서 장애물 조건을 충족하지 않는지 확인한 다음 그에 따라 개수를 늘릴 수 있습니다.

다음은 O(N^2) 시간과 O(N) 추가 공간이 필요한 위 개념에 대한 솔루션을 구현한 것입니다.

C++

// C++ program to find how many mirror can transfer // light from bottom to right #include    using namespace std; // method returns number of mirror which can transfer // light from bottom to right int maximumMirrorInMatrix(string mat[] int N) {  // To store first obstacles horizontally (from right)  // and vertically (from bottom)  int horizontal[N] vertical[N];  // initialize both array as -1 signifying no obstacle  memset(horizontal -1 sizeof(horizontal));  memset(vertical -1 sizeof(vertical));  // looping matrix to mark column for obstacles  for (int i=0; i<N; i++)  {  for (int j=N-1; j>=0; j--)  {  if (mat[i][j] == 'B')  continue;  // mark rightmost column with obstacle  horizontal[i] = j;  break;  }  }  // looping matrix to mark rows for obstacles  for (int j=0; j<N; j++)  {  for (int i=N-1; i>=0; i--)  {  if (mat[i][j] == 'B')  continue;  // mark leftmost row with obstacle  vertical[j] = i;  break;  }  }  int res = 0; // Initialize result  // if there is not obstacle on right or below  // then mirror can be placed to transfer light  for (int i = 0; i < N; i++)  {  for (int j = 0; j < N; j++)  {  /* if i > vertical[j] then light can from bottom  if j > horizontal[i] then light can go to right */  if (i > vertical[j] && j > horizontal[i])  {  /* uncomment this code to print actual mirror  position also  cout << i << ' ' << j << endl; */  res++;  }  }  }  return res; } // Driver code to test above method int main() {  int N = 5;  // B - Blank O - Obstacle  string mat[N] = {'BBOBB'  'BBBBO'  'BBBBB'  'BOOBO'  'BBBOB'  };  cout << maximumMirrorInMatrix(mat N) << endl;  return 0; }

Java

// Java program to find how many mirror can transfer // light from bottom to right import java.util.*; class GFG  {  // method returns number of mirror which can transfer  // light from bottom to right  static int maximumMirrorInMatrix(String mat[] int N)   {  // To store first obstacles horizontally (from right)  // and vertically (from bottom)  int[] horizontal = new int[N];  int[] vertical = new int[N];  // initialize both array as -1 signifying no obstacle  Arrays.fill(horizontal -1);  Arrays.fill(vertical -1);    // looping matrix to mark column for obstacles  for (int i = 0; i < N; i++)   {  for (int j = N - 1; j >= 0; j--)   {  if (mat[i].charAt(j) == 'B')  {  continue;  }  // mark rightmost column with obstacle  horizontal[i] = j;  break;  }  }  // looping matrix to mark rows for obstacles  for (int j = 0; j < N; j++)   {  for (int i = N - 1; i >= 0; i--)   {  if (mat[i].charAt(j) == 'B')   {  continue;  }  // mark leftmost row with obstacle  vertical[j] = i;  break;  }  }  int res = 0; // Initialize result  // if there is not obstacle on right or below  // then mirror can be placed to transfer light  for (int i = 0; i < N; i++)  {  for (int j = 0; j < N; j++)   {  /* if i > vertical[j] then light can from bottom  if j > horizontal[i] then light can go to right */  if (i > vertical[j] && j > horizontal[i])  {  /* uncomment this code to print actual mirror  position also  cout << i << ' ' << j << endl; */  res++;  }  }  }  return res;  } // Driver code public static void main(String[] args)  {  int N = 5;  // B - Blank O - Obstacle  String mat[] = {'BBOBB'  'BBBBO'  'BBBBB'  'BOOBO'  'BBBOB'  };  System.out.println(maximumMirrorInMatrix(mat N)); } } /* This code is contributed by PrinciRaj1992 */

Python3

# Python3 program to find how many mirror can transfer # light from bottom to right # method returns number of mirror which can transfer # light from bottom to right def maximumMirrorInMatrix(mat N): # To store first obstacles horizontally (from right) # and vertically (from bottom) horizontal = [-1 for i in range(N)] vertical = [-1 for i in range(N)]; # looping matrix to mark column for obstacles for i in range(N): for j in range(N - 1 -1 -1): if (mat[i][j] == 'B'): continue; # mark rightmost column with obstacle horizontal[i] = j; break; # looping matrix to mark rows for obstacles for j in range(N): for i in range(N - 1 -1 -1): if (mat[i][j] == 'B'): continue; # mark leftmost row with obstacle vertical[j] = i; break; res = 0; # Initialize result # if there is not obstacle on right or below # then mirror can be placed to transfer light for i in range(N): for j in range(N):    ''' if i > vertical[j] then light can from bottom  if j > horizontal[i] then light can go to right ''' if (i > vertical[j] and j > horizontal[i]):    ''' uncomment this code to print actual mirror  position also''' res+=1; return res; # Driver code to test above method N = 5; # B - Blank O - Obstacle mat = ['BBOBB' 'BBBBO' 'BBBBB' 'BOOBO' 'BBBOB' ]; print(maximumMirrorInMatrix(mat N)); # This code is contributed by rutvik_56.

// C# program to find how many mirror can transfer // light from bottom to right using System;   class GFG  {  // method returns number of mirror which can transfer  // light from bottom to right  static int maximumMirrorInMatrix(String []mat int N)   {  // To store first obstacles horizontally (from right)  // and vertically (from bottom)  int[] horizontal = new int[N];  int[] vertical = new int[N];  // initialize both array as -1 signifying no obstacle  for (int i = 0; i < N; i++)   {  horizontal[i]=-1;  vertical[i]=-1;  }    // looping matrix to mark column for obstacles  for (int i = 0; i < N; i++)   {  for (int j = N - 1; j >= 0; j--)   {  if (mat[i][j] == 'B')  {  continue;  }  // mark rightmost column with obstacle  horizontal[i] = j;  break;  }  }  // looping matrix to mark rows for obstacles  for (int j = 0; j < N; j++)   {  for (int i = N - 1; i >= 0; i--)   {  if (mat[i][j] == 'B')   {  continue;  }  // mark leftmost row with obstacle  vertical[j] = i;  break;  }  }  int res = 0; // Initialize result  // if there is not obstacle on right or below  // then mirror can be placed to transfer light  for (int i = 0; i < N; i++)  {  for (int j = 0; j < N; j++)   {  /* if i > vertical[j] then light can from bottom  if j > horizontal[i] then light can go to right */  if (i > vertical[j] && j > horizontal[i])  {  /* uncomment this code to print actual mirror  position also  cout << i << ' ' << j << endl; */  res++;  }  }  }  return res;  } // Driver code public static void Main(String[] args)  {  int N = 5;  // B - Blank O - Obstacle  String []mat = {'BBOBB'  'BBBBO'  'BBBBB'  'BOOBO'  'BBBOB'  };  Console.WriteLine(maximumMirrorInMatrix(mat N)); } } // This code is contributed by Princi Singh

JavaScript

<script> // JavaScript program to find how many mirror can transfer // light from bottom to right // method returns number of mirror which can transfer // light from bottom to right function maximumMirrorInMatrix(mat N)  {  // To store first obstacles horizontally (from right)  // and vertically (from bottom)  var horizontal = Array(N).fill(-1);  var vertical = Array(N).fill(-1);    // looping matrix to mark column for obstacles  for (var i = 0; i < N; i++)   {  for (var j = N - 1; j >= 0; j--)   {  if (mat[i][j] == 'B')  {  continue;  }  // mark rightmost column with obstacle  horizontal[i] = j;  break;  }  }  // looping matrix to mark rows for obstacles  for (var j = 0; j < N; j++)   {  for (var i = N - 1; i >= 0; i--)   {  if (mat[i][j] == 'B')   {  continue;  }  // mark leftmost row with obstacle  vertical[j] = i;  break;  }  }  var res = 0; // Initialize result  // if there is not obstacle on right or below  // then mirror can be placed to transfer light  for (var i = 0; i < N; i++)  {  for (var j = 0; j < N; j++)   {  /* if i > vertical[j] then light can from bottom  if j > horizontal[i] then light can go to right */  if (i > vertical[j] && j > horizontal[i])  {  /* uncomment this code to print actual mirror  position also  cout << i << ' ' << j << endl; */  res++;  }  }  }  return res; } // Driver code var N = 5; // B - Blank O - Obstacle var mat = ['BBOBB'  'BBBBO'  'BBBBB'  'BOOBO'  'BBBOB' ]; document.write(maximumMirrorInMatrix(mat N)); </script>

산출

시간 복잡도: O(n²).
보조 공간: O(n)