给出了一个方阵，其中每个单元代表空白或障碍物。我们可以把镜子放在空白位置。所有镜子都将位于45度的位置，即如果其路径上没有障碍物，它们可以将光线从底部转移到右侧。 在这个问题中，我们需要计算在正方形矩阵中可以放置多少这样的反射镜，这些反射镜可以将光线从底部转移到右侧。 例如：
null
Output for above example is 2.In above diagram, mirror at (3, 1) and (5, 5) are ableto send light from bottom to right so total possible mirror count is 2.
我们可以通过检查这些反射镜在矩阵中的位置来解决这个问题，可以从底部向右侧传输光的反射镜在其路径上不会有任何障碍物，即。 如果在索引（i，j）处有一面镜子，那么 对于所有k，i
C++
// C++ program to find how many mirror 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 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#
// 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> |
输出：
2
本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
