castle.cpp

USACO Section 2.1的全部AC的代码 OIer专用.

/*
NAME:lemon_c1
LANG:C++
PROG:castle
*/
#include<fstream>
using namespace std;
ifstream cin("castle.in");
ofstream cout("castle.out");
const int di[4]={1,2,4,8};
int m,n;
int e[2501][4];
bool used[2501];
int color[2501];
int s_color[2501];
int ccolor;
inline int tov(int i,int j)
{
	return i*m+j;
}
int dfs(int v);
int main(void)
{
	cin>>m>>n;
	int dv[4]={-1,-m,1,m};
	for(int i=0;i<n;i++)
		for(int j=1;j<=m;j++)
		{
			int t;
			cin>>t;
			for(int k=0;k<4;k++)
				e[tov(i,j)][k]=((di[k]&t)==0)?(tov(i,j)+dv[k]):0;
		}
	int cnt=0;
	for(int i=1;i<=m*n;i++)
		if(!used[i])
		{
			int t=dfs(i);
			s_color[ccolor++]=t;
			if(t>cnt)cnt=t;
		}
	cout<<ccolor<<endl<<cnt<<endl;
	cnt=0;
	int tcol,trow,dir;
	for(int row=1;row<=m;row++)
		for(int col=n-1;col>=0;col--)
		{
			if(col!=0)
				if(color[tov(col,row)]!=color[tov(col-1,row)])
					if(s_color[color[tov(col,row)]]+s_color[color[tov(col-1,row)]]>cnt)
					{
						cnt=s_color[color[tov(col,row)]]+s_color[color[tov(col-1,row)]];
						tcol=col+1;
						trow=row;
						dir=1;
					}
			if(row!=m)
				if(color[tov(col,row)]!=color[tov(col,row+1)])
					if(s_color[color[tov(col,row)]]+s_color[color[tov(col,row+1)]]>cnt)
					{
						cnt=s_color[color[tov(col,row)]]+s_color[color[tov(col,row+1)]];
						tcol=col+1;
						trow=row;
						dir=0;
					}
		}
	cout<<cnt<<endl<<tcol<<' '<<trow<<' '<<((dir==0)?'E':'N')<<endl;
	return 0;
}
int dfs(int v)
{
	if(used[v])return 0;
	color[v]=ccolor;
	used[v]=true;
	int cnt=1;
	for(int i=0;i<4;i++)
		if(e[v][i])
			cnt+=dfs(e[v][i]);
	return cnt;
}