Home > Old Blog Posts > USACO 2.1.1 The Castle

USACO 2.1.1 The Castle


这道题不难,就麻烦在输入输出以及存储。

这道题特殊格式的输入提示我们用位运算战翻它(也可以不用)。

输出时要注意方向。

具体处理上,我们用一个数组来存储每个格子四个方向是否有墙,先进行一次floodfill得出房间个数,再枚举去掉哪一堵墙,每次都 再进行一次floodfill,这种方法的时间复杂度为O(n^2),对付这道题可怜巴巴的数据量足矣。

代码:

/*
ID: dementr1
PROG: castle
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
struct wallllllll
{
bool west,east,south,north,used;
} wall[51][51];
int castle[51][51]={};
int M,N;
ifstream fin(“castle.in”);
ofstream fout(“castle.out”);
void init()
{
int tmp,i,j;
fin>>M>>N;
memset(wall,true,sizeof(wall));
for(i=0;i<N;i++)
for(j=0;j<M;j++)
{
fin>>tmp;
if(tmp>=8)
{
wall[i][j].south=false;
tmp-=8;
}
if(tmp>=4)
{
wall[i][j].east=false;
tmp-=4;
}
if(tmp>=2)
{
wall[i][j].north=false;
tmp-=2;
}
if(tmp>=1)
{
wall[i][j].west=false;
tmp-=1;
}
}
}
void dfs(int i, int j, int color)
{
castle[i][j]=color;
wall[i][j].used=true;
if(wall[i][j].north&&i-1>=0&&!wall[i-1][j].used)
{
dfs(i-1,j,color);
}
if(wall[i][j].south&&i+1<N&&!wall[i+1][j].used)
{
dfs(i+1,j,color);
}
if(wall[i][j].east&&j+1<M&&!wall[i][j+1].used)
{
dfs(i,j+1,color);
}
if(wall[i][j].west&&j-1>=0&&!wall[i][j-1].used)
{
dfs(i,j-1,color);
}
}
int tryir()
{
int i,j,color=0;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
wall[i][j].used=false;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
if(!wall[i][j].used) dfs(i,j,color++);
int size[3000]={};
for(i=0;i<N;i++)
for(j=0;j<M;j++)
size[castle[i][j]]++;
int max=-1;
for(i=0;i<color;i++) if(size[i]>max) max=size[i];
return max;
}
void work()
{
int i,j,color=0;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
wall[i][j].used=false;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
if(!wall[i][j].used) dfs(i,j,color++);
int size[3000]={};
for(i=0;i<N;i++)
for(j=0;j<M;j++)
size[castle[i][j]]++;
int max=-1;
for(i=0;i<color;i++) if(size[i]>max) max=size[i];
fout<<color<<endl<<max<<endl;
max=-1;
int maxi,maxj,tmp;
char maxdir;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
{
if(!wall[i][j].east&&j<M-1&&!wall[i][j+1].west)
{
wall[i][j].east=true;
wall[i][j+1].west=true;
tmp=tryir();
if(tmp>max||(tmp==max&&(j<maxj||(j==maxj&&i>maxi))))
{
max=tmp;
maxi=i;
maxj=j;
maxdir=’E’;
}
wall[i][j].east=false;
wall[i][j+1].west=false;
}
if(!wall[i][j].north&&i>0&&!wall[i-1][j].south)
{
wall[i][j].north=true;
wall[i-1][j].south=true;
tmp=tryir();
if(tmp>max||(tmp==max&&(j<maxj||(j==maxj&&i>maxi)))||(i==maxi&&j==maxj&&maxdir==’E’))
{
max=tmp;
maxi=i;
maxj=j;
maxdir=’N’;
}
wall[i][j].north=false;
wall[i-1][j].south=false;
}
}
fout<<max<<endl<<maxi+1<<” “<<maxj+1<<” “<<maxdir<<endl;
}
int main()
{
init();
work();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: