# 可以從下到右傳輸光線的最大反射鏡 > 原文： [https://www.geeksforgeeks.org/maximum-mirrors-can-transfer-light-bottom-right/](https://www.geeksforgeeks.org/maximum-mirrors-can-transfer-light-bottom-right/) 給出一個方陣，其中每個像元代表一個空白或一個障礙。 我們可以將鏡子放置在空白位置。 所有反光鏡都將以 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 < = N 在索引（k，j）處將不存在障礙 對于所有 k，j <在索引（i，k）中將不存在障礙 k < = N 記住上面的兩個方程，我們可以在給定矩陣的一次迭代中在每一行找到最右邊的障礙物，而在給定矩陣的另一次迭代中在每一列中找到最下面的障礙物。 將這些索引存儲在單獨的數組中之后，我們可以檢查每個索引是否滿足障礙條件，然后相應地增加計數。 以下是基于上述概念的解決方案，需要 O（N ^ 2）時間和`O(n)`額外空間。 ## C++ ```cpp // 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 horizontaly (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; } ```