首页 > 代码库 > 【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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。