Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
For example, consider the below binary matrix.
0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0
The maximum square sub-matrix with all set bits is
1 1 1 1 1 1 1 1 1
Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottommost
entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C]. a) Copy first row and first columns as it is from M[][] to S[][] b) For other entries, use following expressions to construct S[][] If M[i][j] is 1 then S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 Else /*If M[i][j] is 0*/ S[i][j] = 0 2) Find the maximum entry in S[R][C] 3) Using the value and coordinates of maximum entry in S[i], print sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:
0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 2 2 0 1 2 2 3 1 0 0 0 0 0
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.
http://www.geeksforgeeks.org/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/
相关推荐
geeks-for-geeks-solutions:有关Geeks-for-Geeks的问题的解决方案。解决方案可用于C ++
Linux For Non-Geeks - A Hands-On, Project-Based, Take-It-Slow Guidebook 2004
极客换极客 Geeks-For-Geeks 实习文章 使用 scapy 嗅探数据包 - 使用 Javascript 和 DOM 创建棋盘模式 - 如何将链接从一个 iframe 加载到另一个 iframe -
编程挑战:数据结构和算法-编程挑战和提高知识的竞赛
2022最新版:GEEKS V1.0.10主题:在线学习市场WordPress主题.rar
HTML Hello 使用编码编辑器,对于任何4Geeks Academy Student来说,这都是最基本的样板。接下来做什么? 使用 创建一个index.html文件,并通过使用以下命令运行Web服务器来实时查看该文件: $ pip3 install flask &&...
geeks for geeks上的资源,大家下载下,我攒点几分,呵呵。
Geeks2TheRescue:使用MERN的Web App,旨在连接雄心勃勃的开发人员
带有React JS的WebApp样板 要求: 确保您使用的是节点版本10 安装软件包: $ npm install 创建一个.env文件: $ cp .env.example .env 开始编码! 以及具有实时重新加载功能的webpack开发服务器(适用于Windows...
:sparkles: gloomhaven-geeks :sparkles: 这是一个使用Git作为的网站。 它是在不到一分钟的时间内使用创建的。 您可以像这样,或探索一些变体。 如何不同: :artist_palette: 看 :pencil: 内容管理系统 :gear: 静态...
夏季极客提交 这个Web应用程序被配制成在Innnovaccer SDE实习分配的一部分,使用的NodeJS,MongoDB的,NodeMailer的电子邮件和Nexmo的手机信息,根据。 预习 报到表格 结帐电子邮件 使用的技术 ...
关于网络游戏和极客的最新的链接。玩家的必须 简单而美丽。通过网络为您带来最新的游戏新闻,评论,视频和互动。... Geeks Fest将替换您的默认标签,它将成为您的主页,所以您不要不要错过任何东西。 支持语言:English
4Geeks Academy的Javascript练习教程 完整的自动分级和交互式Java练习供有兴趣学习Java的人选择! ←您在这里我们需要你! 这些练习是与您自己的贡献者协作构建和维护的。 如果您发现任何错误或拼写错误,请贡献和/...
geeks_algorithms 极客算法编码问题
下载所有Geeks for Geeks Algo和数据结构教程,并另存为PDF 注意:我写这个脚本是因为我的朋友需要它。 我不确定刮除Geeks4Geeks是否合法。 将来,如果我遇到任何此类政策,我都会毫不犹豫地删除此回购协议。 安装 ...
Ubuntu for Non-Geeks (Fourth Edition)
以团队形式建立网站(Git合作) 在开发... :laptop: 运行网站为了实时观看网站,请运行以下命令: $ npx browser-sync start -s -w部署网站使用Vercel,Netlify或Github页面将网站部署到团队URL(例如: https://mysu
Geeks 算法基础的 Geeks - 围绕算法构建的网站,第 4 版 - 包含摘录、代码和解决方案 - 围绕算法设计手册,第 2 版构建的网站 - 有讲义、程序、算法库、解决方案维基 - COS226 的作业 大 O 符号: C: - 指针 - Beej...
1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好做。 2 使用一个数组记录当前顶点在堆中的位置,相当于一个...