注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1505  

2012-10-19 23:50:57|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1505
题意:在一个二维矩阵里找一个最大的子矩阵,在图中画F的区域里找
这题是1506的一个变形,刚开始自己想了一种办法做,WA了一次就A了,原因是题目给的二维矩阵有点坑爹,会有多余的空格,我是直接按一个空格算的,所以WA了,改了之后就A了~后来上网看人家的做法,都大同小异,运行下发现自己跑出的快了一倍,不过开了挺大的空间……
先介绍普遍的做法吧:构造一个n*m的矩阵h,h[i][j]代表的是以h[i][j]为底的字符'F'的最大高度。就转化成了hdu1506的问题了,对每行进行hdu1506的dp,取最大值。具体代码就不贴了,大家可自行搜~
我的方法有点麻烦,以每个'F'为中心,记录以其中心的上下左右边界(该区域内均是'F'),然后分别以左,右,上,下各遍历一遍,更新边界值,更新方法同1505,不同的是,满足更新条件是需要某个整行或者整列都是'F',比如说现在更新左边界,如果该点左边界左边一格所在的列(高度为该点的上边界到下边界)都是'F'的话,那么更新其值,即是该点的左边界应改为该点左边界左边一格的左边界,下边界,上边界,下边界也是如此

/*
* fudq.cpp
*
* Created on: 2012-10-19

* 更新四个方向的值,满足的条件是边界外的整一列或者整一行(宽度或者高度按该点当前区域算)都是'F'
*/
#include<algorithm>
#include<stdio.h>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<iostream>
using namespace std;
#define N 1010
struct Node
{
int left,right,up,down;
char str;
}node[N][N];

bool judge1(int a,int b,int c)//left+right
{
for(int i=node[a][b].up;i<=node[a][b].down;i++)
if(node[i][c].str!='F')
return false;
return true;
}

bool judge2(int a,int b,int c)//up+down
{
for(int i=node[a][b].left;i<=node[a][b].right;i++)
if(node[c][i].str!='F')
return false;
return true;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
#endif
int T,n,m,i,j,temp,res;
char a[10];
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
scanf("%s",a);
node[i][j].str=a[0];
if(node[i][j].str == 'F')
{
node[i][j].left=j;node[i][j].right=j;
node[i][j].up=i;node[i][j].down=i;
}
}
//init
for(i=0;i<n;i++)
{
node[i][0].str='R';
node[i][m+1].str='R';
}
for(i=0;i<m;i++)
{
node[0][i].str='R';
node[n+1][i].str='R';
}
//left
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(node[i][j].str == 'F')
{
while(judge1(i,j,node[i][j].left-1))/*node[i][node[i][j].left-1].str == 'F'*/
node[i][j].left=node[i][node[i][j].left-1].left;
}
}
//right
for(i=1;i<=n;i++)
for(j=m;j>0;j--)
{
if(node[i][j].str == 'F')
{
while(judge1(i,j,node[i][j].right+1))
node[i][j].right=node[i][node[i][j].right+1].right;
}
}
//up
for(j=1;j<=m;j++)
for(i=1;i<=n;i++)
{
if(node[i][j].str == 'F')
{
while(judge2(i,j,node[i][j].up-1))
node[i][j].up=node[node[i][j].up-1][j].up;
}
}
//down
for(j=1;j<=m;j++)
for(i=n;i>0;i--)
{
if(node[i][j].str == 'F')
{
while(judge2(i,j,node[i][j].down+1))
node[i][j].down=node[node[i][j].down+1][j].down;
}
}
for(i=0,res=0;i<n;i++)
for(j=0;j<m;j++)
{
if(node[i][j].str=='F')
{
temp=(node[i][j].right-node[i][j].left+1)*(node[i][j].down-node[i][j].up+1)*3;
if(temp>res)
res=temp;
}
}
printf("%d\n",res);
}
return 0;
}



  评论这张
 
阅读(269)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018