各セルが空白または障害物を表す正方行列が与えられます。空の位置にミラーを配置できます。すべてのミラーは 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
上記の 2 つの方程式を念頭に置くと、指定された行列の 1 回の反復ではすべての行で右端の障害物を見つけることができ、指定された行列の別の反復ではすべての列で最下位の障害物を見つけることができます。これらのインデックスを別の配列に保存した後、各インデックスで障害物条件を満たしていないかどうかを確認し、それに応じてカウントを増やすことができます。
以下は、O(N^2) 時間と O(N) 個の追加スペースを必要とする上記の概念に基づいて実装されたソリューションです。
C++// C++ program to find how many mirror can transfer // light from bottom to right #include
// 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 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
<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>
出力
2
時間計算量: O(n2）。
補助スペース: O(n)