数据结构
网络
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 次浏览
广告