博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
USACO--2.1The Castle
阅读量:6802 次
发布时间:2019-06-26

本文共 2618 字,大约阅读时间需要 8 分钟。

思路:这个题目难在建图,開始的时候我想把每一个房间没有墙的面求出来,然后再和他邻近的房间加上一条边进行建图,后面发现要通过题目给定的条件求出房间那个面没有墙是十分困难的;后面參考了别人的思路,我们记录每一个房间那几面是有墙的(这个非常easy做到),然后就不显示建图了。直接通过dfs标记的思想求出这个图全部的连通块(Flood fill 算法)。后面的处理就比較简单了,求出这个连通块后就能够知道总共同拥有几个房间了,最大的房间有多大;然后我们再依次试探拆除每一个房间的N,E面的墙壁。看一下能得到的最大房间的数量。

对于题目中:
Choose the optimal wall to remove from the set of optimal walls by choosing the module farthest to the west (and then, if still tied, farthest to the south). If still tied, choose ‘N’ before ‘E’. Name that wall by naming the module that borders it on either the west or south, along with a direction of N or E giving the location of the wall with respect to the module.
这段话,開始的时候我非常是不能理解,后面才知道,他的意思是:在大的方向上我们要优先拆除西面和然后是南面。对于每一个小的房间我们应该优先拆除北面然后是东面。果然是英语太渣。。。

。。。

代码例如以下:

/*ID: 15674811LANG: C++TASK: castle*/#include
#include
#include
#include
using namespace std;///南东北西int dx[]={
1,0,-1,0};int dy[]={
0,1,0,-1};///西南北东///int dx1[]={0,1,-1,0};///int dy1[]={-1,0,0,1};///北东int dx1[]={-1,0};int dy1[]={
0,1};int vis[55][55],n,m;char name[]={
'N','E'};typedef struct{ bool flag[5];}P;P p[55][55];void dfs(int x,int y,int flag){ for(int k=0;k<4;k++) { if(p[x][y].flag[k]) continue; int xx=x+dx[k]; int yy=y+dy[k]; if(xx<1||xx>n||yy<1||yy>m) continue; if(vis[xx][yy]) continue; vis[xx][yy]=flag; dfs(xx,yy,flag); }}int main(){ ofstream fout("castle.out"); ifstream fin("castle.in"); //ifstream fin("lkl.txt"); while(fin>>m>>n) { memset(p,0,sizeof(p)); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int x; fin>>x; if(x>=8) p[i][j].flag[0]=true,x-=8; if(x>=4) p[i][j].flag[1]=true,x-=4; if(x>=2) p[i][j].flag[2]=true,x-=2; if(x>=1) p[i][j].flag[3]=true; } int cnt=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(vis[i][j]) continue; vis[i][j]=++cnt; dfs(i,j,cnt); } int num[3000]; memset(num,0,sizeof(num)); int Max=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { num[vis[i][j]]++; Max=max(Max,num[vis[i][j]]); } fout<
<
<
<
n||yy<1||yy>m) continue; if(vis[x][y]==vis[xx][yy]) continue; int tmp=num[vis[x][y]]+num[vis[xx][yy]]; if(room

转载地址:http://qdjwl.baihongyu.com/

你可能感兴趣的文章
算法笔记--归并排序
查看>>
ACM-ICPC 2018 沈阳赛区网络预赛 J Ka Chang
查看>>
软件工程——第一次作业(2019)
查看>>
ssh公钥
查看>>
django用户认证系统——注销和页面跳转5
查看>>
软件设计师01-计算机组成原理与体系结构
查看>>
iOS --开发笔记:关于手机号码的判断【转】
查看>>
招商银行的企业网银如何完成银企对账
查看>>
转--快速学习法:一年学完MIT计算机课程
查看>>
多标签分类
查看>>
Python基础教程(第2版 修订版) pdf
查看>>
VS快捷键
查看>>
各种字符集和编码详解
查看>>
dubbo原理
查看>>
SQL server 清除缓存
查看>>
python实现常见排序算法
查看>>
listctrl加入图标
查看>>
gem 更新源设置,ruby安装
查看>>
码农们:我们才是真正的土豪!
查看>>
[Node.js]NPM 使用
查看>>