C++程序 查找所有填充为0的矩形

C++程序 查找所有填充为0的矩形

我们有一个2D数组,填充有0和1。我们需要查找所有填充为0的矩形的起始点和结束点。已知矩形是分离的,不会相互触碰,但它们可以与数组的边界相接触。一个矩形可能只包含一个元素。

示例:

input = [
            [1, 1, 1, 1, 1, 1, 1],
            [1, 1, 1, 1, 1, 1, 1],
            [1, 1, 1, 0, 0, 0, 1],
            [1, 0, 1, 0, 0, 0, 1],
            [1, 0, 1, 1, 1, 1, 1],
            [1, 0, 1, 0, 0, 0, 0],
            [1, 1, 1, 0, 0, 0, 1],
            [1, 1, 1, 1, 1, 1, 1]
        ]


Output:
[
  [2, 3, 3, 5], [3, 1, 5, 1], [5, 3, 6, 5]
]

Explanation:
我们在这里有三个矩形,起始位置分别为
(2, 3), (3, 1), (5, 3)
Input = [
            [1, 0, 1, 1, 1, 1, 1],
            [1, 1, 0, 1, 1, 1, 1],
            [1, 1, 1, 0, 0, 0, 1],
            [1, 0, 1, 0, 0, 0, 1],
            [1, 0, 1, 1, 1, 1, 1],
            [1, 1, 1, 0, 0, 0, 0],
            [1, 1, 1, 1, 1, 1, 1],
            [1, 1, 0, 1, 1, 1, 0]
        ]
Output:
[
  [0, 1, 0, 1], [1, 2, 1, 2], [2, 3, 3, 5], 
  [3, 1, 4, 1], [5, 3, 5, 6], [7, 2, 7, 2], 
  [7, 6, 7, 6]
]

步骤1:逐行和逐列查找0.

步骤2:当你遇到任何0时,在输出数组中保存它的位置,并使用循环将所有相关的0改为这个位置的任何常见数字,这样我们可以在下一次处理时将其排除在外。

步骤3:当你在步骤2中改变所有相关的0时,在输出数组中以相同的索引存储最后处理的0的位置。

步骤4:当你触碰到边缘时特别小心,不要减去-1,因为循环已经在确切的位置上中断了。

下面是实现以上方法的代码:

// C++程序为上述方法
 
#include<bits/stdc++.h>
 
使用命名空间std;
 
void findend(int i,int j,vector<vector<int> >& a,
             vector<vector<int> >& output,int index)
{
    int x = a.size();
    int y = a[0].size();
 
    //标志检查列边缘情况,
    //初始化为0
    int flagc = 0;
 
    //标志检查行边缘情况,
    //初始化为0
    int flagr = 0;
    int n,m;
 
    for(m = i; m< x; m ++){
 
        //循环中断了第一次遭遇1
        if(a [m] [j] == 1){
            flagr = 1; //设置标志
            休息;
        }
 
        //通过,因为已经处理过
        if(a [m] [j] == 5)
            继续;
 
        for(n = j; n< y; n ++){
            //循环中断了第一次遭遇1
            if(a [m] [n] == 1){
                flagc = 1; //设置标志
                休息;
            }
 
            //填充矩形元素与任何
            //数字,以便我们可以排除
            //下次
            a [m] [n] = 5;
        }
    }
 
    if(flagr == 1)
        output [index] .push_back(m-1);
    否则
        //当终点接触边界时
        output [index] .push_back(m);
 
    if(flagc == 1)
        output [index] .push_back(n-1);
    否则
        //当终点接触边界时
        output [index] .push_back(n);
}
 
void get_rectangle_coordinates(vector<vector<int> > a)
{
 
    //检索数组的列大小
    int size_of_array = a.size();
 
    //输出数组,我们将去
    //存储我们的输出
    vector<vector<int> > output;
 
    //它将用于存储开始
    //和结束位置在同一索引中
    int index = -1;
 
    for(int i = 0; i< size_of_array; i ++){
        for(int j = 0; j< a [0] .size(); j ++){
            if(a [i] [j] == 0){
 
                //存储矩形的初始位置
                输出.push_back({i,j});
 
                //将用于
                //上一个位置
                index = index +1;
                findend(i,j,a,output,index);
            }
        }
    }
 
    cout<<“ [”;
    int aa = 2,bb = 0;
 
    for(auto i:output){
        bb = 3;
        cout<<“ [”;
        for(int j:i){
            if(bb)
                cout<< j<<“,”;
            其他
                cout<< j;
            bb--;
        }
                cout<<“]”;
        如果(aa)
            cout<<“,”;
        aa--;
    }
    cout<<“]”;
}
 
//驱动程序
int main()
{
    vector<vector<int> > tests = {
        {1,1,1,1,1,1,1},{1,1,1,1,1,1,1},
        {1,1,1,0,0,0,1},{1,0,1,0,0,0,1},
        {1,0,1,1,1,1,1},{1,0,1,0,0,0,0},
        {1,1,1,0,0,0,1},{1,1,1,1,1,1,1}
    };
 
    get_rectangle_coordinates(tests);
 
    返回0;
}
 
//此代码由mohit kumar 29贡献。```  

输出:

[[2, 3, 3, 5],[3, 1, 5, 1],[5, 3, 6, 5]]

时间复杂度:O(n ^ 2)

空间复杂度:O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例