hdu 1937 Finding Seats
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 889 Accepted Submission(s): 290
The movie theater has R rows of C seats each, and they can see a map with the currently available seats marked. They decided that seating close to each other is all that matters, even if that means seating in the front row where the screen is so big it’s impossible to see it all at once. In order to have a formal criteria, they thought they would buy seats in order to minimize the extension of their group.
The extension is defined as the area of the smallest rectangle with sides parallel to the seats that contains all bought seats. The area of a rectangle is the number of seats contained in it.
They’ve taken out a laptop and pointed at you to help them find those desired seats.
Input is terminated with R = C = K = 0.
...XX
.X.XX
XX...
5 6 6
..X.X.
.XXX..
.XX.X.
.XXX.X
.XX.XX
0 0 0
9
#include <iostream>
#include <cstdio>
#define MAX 300
using namespace std;
int r,c,k;
int sum[MAX + ][MAX + ];
inline int get(int l1,int l2,int r1,int r2) {
return sum[l2][r2] - sum[l1 - ][r2] - sum[l2][r1 - ] + sum[l1 - ][r1 - ];
}
int main() {
while(~scanf("%d%d%d",&r,&c,&k) && r && c && k) {
int ans = r * c + ;
for(int i = ;i <= r;i ++) {
getchar();
for(int j = ;j <= c;j ++) {
char ch = getchar();
if(ch == '.') sum[i][j] = ;
else sum[i][j] = ;
sum[i][j] += sum[i - ][j] + sum[i][j - ] - sum[i - ][j - ];
}
}
for(int i = ;i <= r;i ++) {
for(int j = ;j <= r;j ++) {
int left = ,right = ;
while(right <= c && left <= right) {
if(get(i,j,left,right) < k) right ++;
else {
ans = min(ans,(j - i + ) * (right - left + ));
left ++;
}
}
}
}
printf("%d\n",ans);
}
}
最新文章
- Oracle 第一天
- 通过样式class 判断多个checkbox redio 是否都选中
- ural 1110,快速幂
- grunt下cssmin的配置参数
- 杀死MySQL的连接
- Delphi -- 创建 桌面、发送到...、快速启动栏、开始菜单、程序菜单、右键菜 单
- 入我新美大的Java后台开发面试题总结
- [ 面试没回答上的问题2]IOS上给body绑定click事件的bug
- firefox中遇到的offsetX的问题
- end to end testing
- SKU : Stock Keeping Unit
- Django启动报错笔记
- Day3 -4.9!受到毕设的突然袭击,一脸蒙蔽,学习暂时停止,明晚继续
- 【转】WPF自定义控件与样式(4)-CheckBox/RadioButton自定义样式
- pytest.7.常见套路
- FinalizableReference, FinalizablePhantomReference, FinalizableReferenceQueue
- linux中查看某个端口(port)
- eclipse debug 执行到断点处并没有停下,断点无效问题
- 关于对象的 width offsetwidth availWidth scrollHeight
- 不可不看!CSS3中三十一种选择器用法