資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中從底部到右側傳輸光的最大反射鏡數量
給定一個只包含 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，下方沒有行，右側沒有列。
下面程式中使用的辦法如下
陣列 Arr[][] 用於表示 0 和 1 的矩陣。
函式 maximumMirror(int mat[][], int n) 以矩陣及其邊長 n 作為輸入，並返回可以放置的最大反射鏡數量，如上所示。
變數 flag 用於標記 arr [i] [j] 下方或右側單元格中是否存在障礙物。
Count 用於表示反射鏡的數量，最初為 0。
從索引 0,0 遍歷矩陣。
對於每個單元格，如果它是空的（可以放置反射鏡），則檢查下面的單元格（k=i+1 到 n-1）。如果任何 arr[k][j] 是障礙物（值=1），則中斷 while 迴圈並將 flag 標記為 1。如果不是，則繼續檢查右側的單元格（l=j+1 到 n-1）。
如果存在障礙物，則設定 flag。
兩個 while 迴圈結束後，如果 flag 為 0，則遞增 count，因為可以放置反射鏡。
返回 count 作為最大反射鏡的數量。
示例
// 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
更新於: 2020-07-28
113 次瀏覽
廣告