vijos 1057 盖房子 简单DP
2024-08-31 21:59:00
描述
永恒の灵魂最近得到了面积为n*m的一大块土地(高兴ING^_^),他想在这块土地上建造一所房子,这个房子必须是正方形的。
但是,这块土地并非十全十美,上面有很多不平坦的地方(也可以叫瑕疵)。这些瑕疵十分恶心,以至于根本不能在上面盖一砖一瓦。
他希望找到一块最大的正方形无瑕疵土地来盖房子。
不过,这并不是什么难题,永恒の灵魂在10分钟内就轻松解决了这个问题。
现在,您也来试试吧。
格式
输入格式
输入文件第一行为两个整数n,m(1<=n,m<=1000),接下来n行,每行m个数字,用空格隔开。0表示该块土地有瑕疵,1表示该块土地完好。
输出格式
一个整数,最大正方形的边长。
限制
各点时限均为1s。
题意:找一个最大的正方形。
思路:很简单的一个思路,从左,上,左上方向转移即可,状态设计为地图为i X j时的最大正方形边长。
/** @Date : 2016-12-13-19.39
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version :
*/
#include<bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std; const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8; int dp[1010][1010];
int main()
{
int n, m;
cin >> n >> m;
MMF(dp);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
scanf("%d", &dp[i][j]);
}
}
int ma = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
if(dp[i][j] != 0)
{
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
}
ma = max(dp[i][j], ma);
}
}
printf("%d\n", ma);
return 0;
}
最新文章
- Mysql 中 show full processlist
- ActiveMQ笔记(2):基于ZooKeeper的HA方案
- CSS侧边栏,ng-click定义选中事件
- C#数组的声明方式
- 如何获取EntityManager
- c#中结构体(struct)和类(class)的区别
- 【UESTC 482】Charitable Exchange(优先队列+bfs)
- hihoCoder #1127:二分图最小点覆盖和最大独立集
- ecshop 优化_将商品详情页goods.php重命名为shangpin.php
- Jquery实现文本框获取焦点清空内容,失去焦点重新获得内容的公共函数
- windows命令行编码与nodejs编码格式冲突的解决方式
- c#中从string数组转换到int数组
- JAVA类的方法调用和变量(全套)
- P1177 【模板】快速排序 题解
- python基础自学 第三天
- 054 kafka内部机制
- Spring-Mybatis依赖
- 转 Visual C++6.0 与matlab联合编程(2)----Visual C++6.0 环境下编译和调试MEX文件
- [Element-UI] 使用Element-UI的DateTimePicker组件报错:Cannot read property &#39;getHours&#39; of undefined
- ubuntu18.04配置nvidia docker和远程连接ssh+远程桌面连接(二)
热门文章
- HADOOP docker(八):hadoop本地库
- php中array_map和array_walk的使用对比
- 菜鸟的飞翔日记-os篇
- React &; event-pooling &; bug
- libsvm 用在 婚介数据集中 预测 用户配对
- [LOJ2983] [WC2019] 数树
- hihoCoder#1698 : 假期计划 组合数
- Java异常捕捉
- BZOJ2555:SubString——题解
- HDU4757:Tree——题解