HDU 4328 Contest 3
2024-08-31 08:37:39
悬线法可解，稍有点烦琐。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
using namespace std; char map[1010][1010];
int lefts[1010][1010],heights[1010][1010],rights[1010][1010]; int CountSingle(int n,int m,char sing){
int ret=0;
for(int i=1;i<=n;i++){
if(i==1){
int l=0;
for(int j=1;j<=m;j++){
if(map[i][j]!=sing){
heights[i][j]=0;
lefts[i][j]=m+1;
l=j;
}
else{
heights[i][j]=1;
lefts[i][j]=l+1;
}
}
int r=m+1;
for(int j=m;j>=1;j--){
if(map[i][j]!=sing){
rights[i][j]=0;
r=j;
}
else{
rights[i][j]=r-1;
ret=max(ret,heights[i][j]*2+2*(rights[i][j]-lefts[i][j]+1));
}
}
}
else{
int l=0;
for(int j=1;j<=m;j++){
if(map[i][j]!=sing){
heights[i][j]=0;
lefts[i][j]=m+1;
l=j;
}
else{
if(map[i-1][j]==sing){
heights[i][j]=heights[i-1][j]+1;
lefts[i][j]=max(lefts[i-1][j],l+1);
}
else{
heights[i][j]=1;
lefts[i][j]=l+1;
}
}
}
int r=m+1;
for(int j=m;j>=1;j--){
if(map[i][j]!=sing){
rights[i][j]=0;
r=j;
}
else{
if(map[i-1][j]==sing){
rights[i][j]=min(rights[i-1][j],r-1);
ret=max(ret,heights[i][j]*2+2*(rights[i][j]-lefts[i][j]+1));
}
else{
rights[i][j]=r-1;
ret=max(ret,heights[i][j]*2+2*(rights[i][j]-lefts[i][j]+1));
}
}
}
}
}
return ret;
} int CountCross(int n,int m){
int ret=0;
for(int i=1;i<=n;i++){
if(i==1){
int l=0;
for(int j=1;j<=m;j++){
if(j==1){
heights[i][j]=1;
lefts[i][j]=1;
}
else{
if(map[i][j-1]==map[i][j]){
lefts[i][j]=j;
l=j-1;
heights[i][j]=1;
}
else{
lefts[i][j]=l+1;
heights[i][j]=1;
}
}
}
int r=m+1;
for(int j=m;j>=1;j--){
if(j==m){
heights[i][j]=1;
rights[i][j]=m;
}
else{
if(map[i][j]==map[i][j+1]){
heights[i][j]=1;
rights[i][j]=j;
r=j+1;
}
else{
rights[i][j]=r-1;
heights[i][j]=1;
}
}
ret=max(ret,heights[i][j]*2+2*(rights[i][j]-lefts[i][j]+1));
}
}
else{
int l=0;
for(int j=1;j<=m;j++){
if(j==1){
if(map[i][j]!=map[i-1][j]){
heights[i][j]=heights[i-1][j]+1;
lefts[i][j]=1;
}
else{
heights[i][j]=1;
lefts[i][j]=1;
}
}
else{
if(map[i][j]!=map[i-1][j]){
heights[i][j]=heights[i-1][j]+1;
if(map[i][j]==map[i][j-1]){
lefts[i][j]=j;
l=j-1;
}
else{
lefts[i][j]=max(lefts[i-1][j],l+1);
}
}
else{
heights[i][j]=1;
if(map[i][j]==map[i][j-1]){
lefts[i][j]=j;
l=j-1;
}
else{
lefts[i][j]=l+1;
}
}
}
}
int r=m+1;
for(int j=m;j>=1;j--){
if(j==m){
if(map[i][j]!=map[i-1][j]){
heights[i][j]=heights[i-1][j]+1;
rights[i][j]=m;
}
else{
heights[i][j]=1;
rights[i][j]=m;
}
}
else{
if(map[i][j]!=map[i-1][j]){
heights[i][j]=heights[i-1][j]+1;
if(map[i][j]==map[i][j+1]){
rights[i][j]=j;
r=j+1;
}
else{
rights[i][j]=min(rights[i-1][j],r-1);
}
}
else{
heights[i][j]=1;
if(map[i][j]==map[i][j+1]){
rights[i][j]=j;
r=j+1;
}
else{
rights[i][j]=r-1;
}
}
}
ret=max(ret,heights[i][j]*2+2*(rights[i][j]-lefts[i][j]+1));
}
}
}
return ret;
} int main(){
int ansR,ansB,ansC,kase=0;
int T,n,m;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
getchar();
for(int i=1;i<=n;i++)
gets(map[i]+1);
ansR=CountSingle(n,m,'R');
ansB=CountSingle(n,m,'B');
ansC=CountCross(n,m);
/* for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++)
cout<<heights[i][j]<<' ';
cout<<endl;
}
cout<<endl;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++)
cout<<lefts[i][j]<<' ';
cout<<endl;
}
cout<<endl;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++)
cout<<rights[i][j]<<' ';
cout<<endl;
}
cout<<ansC<<endl;*/
cout<<"Case #"<<++kase<<": "<<max(ansR,max(ansB,ansC))<<endl;
}
return 0;
}
最新文章
- [转]''\\=DevExpress 中 汉化包 汉化方法
- 一个textview实现文字在图片上面的效果
- 【linux】常见的网络管理命令
- Flink Program Guide （10） -- Savepoints （DataStream API编程指导 -- For Java）
- WPF中的布局控件（转）
- CCIE路由实验(7) -- MPLS VPN
- windows上定时执行php文件
- Mybatis源码解析-MapperRegistry注册mapper接口
- Python文件复制（txt文件）
- [转]Oracle 重建索引的必要性
- int指令
- 听《津津乐道》ThinkPad专题节目有感
- Excel表格中依据某一列的值，将这列中一样的数据放在一个文件中。
- C语言错题集
- Java设计模式学习记录-状态模式
- ROIAlign, ROIPooling及ROIWarp对比
- C#程序优化的50种方案
- How to modify analog output range of Arduino Due
- wannafly 17D 01序列2
- 使用 VS2012 开发 IDA GUI 插件 WIN32 SDK 和 内置函数 AskUsingForm_c