首页 > 代码库 > 城堡——搜索,稍微有点水,令人惊异的是被洛谷评为提高+
城堡——搜索,稍微有点水,令人惊异的是被洛谷评为提高+
此题在Openjudge NOI 上面还有一个阉割版,也就是只求最大房间大小和房间总数量,在2.5搜索专题里面。阉割版不需要多思考就可以做出来,不过原版也只是在想一步而已,鉴于数据不是特别大。可以看到我的做法就是先BFS 算房间,把每个块所属的房间和大小记录好,然后再 按 顺 序 枚举每个块,从而得出做大合并房间和推倒位置。判断墙的存在时用了位运算,因为题目的1248明显就是暗示要这么搞最方便。
1 #include<queue> 2 #include<iostream> 3 using namespace std; 4 const int N=64,ax[]={0,0,1,-1,0},ay[]={0,-1,0,0,1},dr[]={0,1,8,2,4}; 5 const char conv[]={‘\0‘,‘W‘,‘S‘,‘N‘,‘E‘}; 6 struct pnt{int x,y;pnt(int n1,int n2):x(n1),y(n2){}}; 7 int r,c,arg[N][N]; 8 int rooms=1,largest,ans,fnx,fny,fnd,size[N],code[N][N]; 9 bool bfsed[N][N]; 10 int bfs(int sx,int sy){ 11 int res=1; 12 queue<pnt> q; 13 q.push(pnt(sx,sy)); 14 bfsed[sx][sy]=true; 15 code[sx][sy]=rooms; 16 while(!q.empty()){ 17 int x=q.front().x,y=q.front().y; 18 q.pop(); 19 for(int i=1;i<=4;i++){ 20 int nx=x+ax[i],ny=y+ay[i]; 21 if(nx<1||nx>r||ny<1||ny>c||bfsed[nx][ny]||arg[x][y]&dr[i])continue; 22 res++; 23 bfsed[nx][ny]=true; 24 code[nx][ny]=rooms; 25 q.push(pnt(nx,ny)); 26 } 27 } 28 return res; 29 } 30 int main(){ 31 cin>>c>>r; 32 for(int i=1;i<=r;i++) 33 for(int j=1;j<=c;j++) 34 cin>>arg[i][j]; 35 for(int i=1;i<=r;i++) 36 for(int j=1;j<=c;j++) 37 if(!bfsed[i][j]) 38 largest=max(largest,size[rooms]=bfs(i,j)),rooms++; 39 for(int j=c;j>=1;j--) 40 for(int i=1;i<=r;i++){ 41 if(i>1&&(arg[i][j]&2)&&code[i][j]!=code[i-1][j]){ 42 if(size[code[i-1][j]]+size[code[i][j]]>=ans){ 43 ans=size[code[i-1][j]]+size[code[i][j]]; 44 fnx=i;fny=j;fnd=3; 45 } 46 } 47 else if(j<c&&(arg[i][j]&4)&&code[i][j]!=code[i][j+1]){ 48 if(size[code[i][j+1]]+size[code[i][j]]>=ans){ 49 ans=size[code[i][j+1]]+size[code[i][j]]; 50 fnx=i;fny=j;fnd=4; 51 } 52 } 53 } 54 cout<<rooms-1<<endl<<largest<<endl<<ans<<endl 55 <<fnx<<" "<<fny<<" "<<conv[fnd]<<endl; 56 return 0; 57 }
洛谷上3ms。
城堡——搜索,稍微有点水,令人惊异的是被洛谷评为提高+
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。