首页 > 代码库 > 【USACO 2.1】The Castle

【USACO 2.1】The Castle

/*TASK: castleLANG: C++SOLVE: 深搜,注意每个方向对应值。枚举去掉的墙,然后再dfs,注意墙要复原,并且dfs里要判断是否超出边界。 */#include<cstdio>#include<algorithm>#include<cstring>#define N 55using namespace std;int n,m;int a[N][N];int ans,num,cnt;int rans,rm,d;char dir[5]="WNES";int v[N][N];int dx[5]={0,-1,0,1},	dy[5]={-1,0,1,0};void dfs(int x,int y){	if(!x||!y||x>n||y>m)return;	if(v[x][y])return;	v[x][y]=1;	num++;	for(int i=0;i<4;i++)		if((a[x][y]&(1<<i))==0)			dfs(x+dx[i],y+dy[i]);}int main(){	freopen("castle.in","r",stdin);	freopen("castle.out","w",stdout);	scanf("%d%d",&m,&n);	for(int i=1;i<=n;i++)		for(int j=1;j<=m;j++)			scanf("%d",&a[i][j]);	for(int i=1;i<=n;i++)		for(int j=1;j<=m;j++)			if(!v[i][j]){				num=0;				cnt++;				dfs(i,j);				ans=max(ans,num);			}	for(int j=1;j<=m;j++)		for(int i=n;i;i--)			for(int k=0;k<4;k++)				if(a[i][j]&(1<<k)){					a[i][j]&=~(1<<k);					num=0;					memset(v,0,sizeof v);					dfs(i,j);					if(num>rans){						rans=num;						rm=i*(m+1)+j;						d=k;					}					a[i][j]|=1<<k;				}	printf("%d\n%d\n%d\n%d %d %c\n",cnt,ans,rans,rm/(m+1),rm%(m+1),dir[d]);	}

  

【USACO 2.1】The Castle