首页 技术 正文
技术 2022年11月23日
0 收藏 665 点赞 4,413 浏览 2281 个字

F – Finding Seats

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status Practice HDU 1937

Description

A group of K friends is going to see a movie. However, they are too late to get good tickets, so they are looking for a good way to sit all nearby. Since they are all science students, they decided to come up with an optimization problem instead of going on with informal arguments to decide which tickets to buy.

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

Each test case will consist on several lines. The first line will
contain three positive integers R, C and K as explained above (1 <=
R,C <= 300, 1 <= K <= R × C). The next R lines will contain
exactly C characters each. The j-th character of the i-th line will be
‘X’ if the j-th seat on the i-th row is taken or ‘.’ if it is available.
There will always be at least K available seats in total.

Input is terminated with R = C = K = 0.  

Output

For each test case, output a single line containing the minimum extension the group can have.  

Sample Input

3 5 5
…XX
.X.XX
XX…
5 6 6
..X.X.
.XXX..
.XX.X.
.XXX.X
.XX.XX
0 0 0  

Sample Output

6
9    

#include<stdio.h>
#include<string.h>
int map[][];
char str[][];
int tmin,k;
int calculate(int x1,int y1,int x2,int y2){
int point=map[x1][y1]-map[x2-][y1]-map[x1][y2-]+map[x2-][y2-];//判断这一范围内的顶点数
int area=(x1-x2+)*(y1-y2+);//判断这一范围内的面积
if(point>=k&&area<tmin)//如果顶点数足够并且面积可以缩小,则更新最小值
tmin=area;
return point;
}
int main(){
int x,y;
while(scanf("%d%d%d",&x,&y,&k)!=EOF){
if(x==&&y==&&k==)
break;
memset(str,,sizeof(str));
memset(map,,sizeof(map));
getchar();
for(int i=;i<=x;i++){
scanf("%s",str[i]+);
getchar();
int sum=;
for(int j=;j<=y;j++){
if(str[i][j]=='.')
sum++;
map[i][j]=map[i-][j]+sum;//构建map数组,类似于动态规划的思想
}
}
tmin=;
for(int x1=x;x1>=;x1--){//从下到上
if(map[x1][y]<k)
break;
for(int x2=;x2<=x1;x2++){//从上到下
if(map[x1][y]-map[x2-][y]<k)
break;
int y1=,y2=;
while(y1<=y&&y2<=y){//两个顶点从左到右
if(calculate(x1,y1,x2,y2)>=k)
y2++; else{
if(y1==y)
break;
y1++;
}
}
}
} printf("%d\n",tmin);
}
return ;
}

    

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:8,727
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,331
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,158
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,978
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,620
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,639