美文网首页C语言C++
寻找最大子方阵

寻找最大子方阵

作者: 一书and一世界 | 来源:发表于2016-12-16 16:29 被阅读64次

题目描述

给定一个元素为0或1的方阵,编写一个程序,找出其中最大的子方阵,使得该子方阵的元素都是1。程序先提示用户输入矩阵的行数,然后提示用户输入矩阵内容,打印输出最大子方阵的第一个元素的位置以及最大子方阵的行数。假定矩阵最多有100行。下面是样例运行:

Enter the number of rows for the matrix: 5  ~Enter
Enter the matrix row by row:
1  0  1  0  1  ~Enter
1  1  1  0  1  ~Enter
1  0  1  1  1  ~Enter
1  0  1  1  1  ~Enter
1  0  1  1  1  ~Enter
The maximum square submatrix is at (2,2) with size 3

程序中应实现下面的函数来寻找最大子方阵:
vector <int> findLargestBlock (const vector <vector <int>> & m)
返回值是一个向量,包含3个值,前两个值代表该最大子方阵第一个元素的行标和列标,第三个值表示该最大子方阵的行数。

C++代码

main.cpp

没用什么优化算法,暴力解题。

#include <iostream>
#include <vector>

using namespace std;

vector <int> findLargestBlock (const vector <vector <int> > &m,int n){
    int t = 1;
    int i = 0,j = 0,l = 0;
    int x = 0,y = 0;
    vector<int> result(3,0);

    for(l=n;l>=1;l--){ //矩阵维数,从最大开始
        for(i=0;i<=n-l;i++){
            for(j=0;j<=n-l;j++){
                t=1;
                for(x=i;x<i+l;x++){
                    for(y=j;y<j+l;y++){
                        if(m[x][y]!=1){    //不为1退出此轮循环
                            t=0;
                            break;
                        }
                    }
                    if(t==0) break;
                }
                if(t==1) break;
            }
            if(t==1) break;
        }
        if(t==1) break;
    }

    result[0] = i;
    result[1] = j;
    result[2] = l;

    return result;
}

int main() {

    int n;
    vector<vector <int> > m(100,vector<int>(100,0));
    cout << "Enter the number of rows for the matrix:";
    cin >> n;
    cout << "Enter the matrix row by row:" << endl;
    int numOfOne = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cin >> m[i][j];
        }
    }
    vector<int> result =  findLargestBlock(m,n);

    cout << "横坐标:" << result[0] << " 纵坐标:" << result[1] << " 最大子方阵的行数:" << result[2] << endl;
    return 0;
}

相关文章

  • 寻找最大子方阵

    题目描述 给定一个元素为0或1的方阵,编写一个程序,找出其中最大的子方阵,使得该子方阵的元素都是1。程序先提示用户...

  • 面试题 17.23. 最大黑方阵

    给定一个方阵,其中每个单元(像素)非黑即白。设计一个算法,找出 4 条边皆为黑色像素的最大子方阵。 返回一个数组 ...

  • LeetCode(03)Longest Substring Wi

    本题的意思是寻找没有重复字符的最大子串,并返回最大子串的长度。题目中已经给出了Example了。下面就是对问题的分...

  • 最大子数组问题

    最近在看算法导论,看到计算最大子数组问题,于是写了一个iOS版本的。 利用分治策略,逐层寻找 最大子数组存在三种情...

  • 动态规划

    求最大子数组,最大子乘积

  • 方阵问题

    一、问题描述 方阵就是正方形队列,行列数相同,比如5×5方阵就表示5行5列的正方形队列。 方阵问题最常见的就是求最...

  • 《方阵》

    文/陈雄辉 我踟蹰在这方阵里 承受着钢筋水泥的凝固和冰冷 没有一种思路像炊烟一样柔软 没有一种表达像乡愁一样自然 ...

  • 方阵

    白云、丛兰、诗香、菩提、碧漪…… 收获、小窗、眉长、汤河、细雨 甲虫、她她、寒秋、安然、旖旎 枫红、南飞、月明、频...

  • 运动会(原文)

    11月10日星期五,我们学校举行了运动会。 先是走方阵,鲜花方阵,红旗方阵,然后是几个班级的方阵。我在走方阵时忘了...

  • 2018年Java方向C组第三题

    标题:字母阵列 仔细寻找,会发现:在下面的8x8的方阵中,隐藏着字母序列:"LANQIAO"。SLANQIAOZO...

网友评论

    本文标题:寻找最大子方阵

    本文链接:https://www.haomeiwen.com/subject/bhgnmttx.html