首页 > 代码库 > bzoj4395[Usaco2015 dec]Switching on the Lights*
bzoj4395[Usaco2015 dec]Switching on the Lights*
bzoj4395[Usaco2015 dec]Switching on the Lights
题意：
n*n个房间，奶牛初始在(1,1)，且只能在亮的房间里活动。每当奶牛经过一个房间，就可以打开这个房间里控制其它房间灯的开关。问奶牛最多可点亮多少个房间。n≤100。
题解：
因为只要一个房间灯亮了，它将一直亮着，所以可以做bfs，每次由队列中的节点扩展可以到的节点。然而这样做不行，因为可能之前尝试过不能到达的房间的灯可以在之后到达的房间里被打开。解决方法是不停做bfs，直到答案不再更新。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 110 7 using namespace std; 8 9 inline int read(){10 char ch=getchar(); int f=1,x=0;11 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}12 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();13 return f*x;14 }15 struct nd{int x,y,n;}nds[maxn*200]; int g[maxn][maxn];16 int n,m,ans; bool lg[maxn][maxn],vis[maxn][maxn]; queue<pair<int,int> >q;17 void bfs(int x,int y){18 while(!q.empty())q.pop(); memset(vis,0,sizeof(vis)); q.push(make_pair(x,y)); vis[x][y]=1;19 for(int i=g[x][y];i;i=nds[i].n)if(!lg[nds[i].x][nds[i].y])lg[nds[i].x][nds[i].y]=1,ans++;20 while(!q.empty()){21 int nowx=q.front().first,nowy=q.front().second; q.pop();22 if(nowx>1&&lg[nowx-1][nowy]&&!vis[nowx-1][nowy]){23 q.push(make_pair(nowx-1,nowy)); vis[nowx-1][nowy]=1;24 for(int i=g[nowx-1][nowy];i;i=nds[i].n)25 if(!lg[nds[i].x][nds[i].y])lg[nds[i].x][nds[i].y]=1,ans++;26 }27 if(nowx<n&&lg[nowx+1][nowy]&&!vis[nowx+1][nowy]){28 q.push(make_pair(nowx+1,nowy)); vis[nowx+1][nowy]=1;29 for(int i=g[nowx+1][nowy];i;i=nds[i].n)30 if(!lg[nds[i].x][nds[i].y])lg[nds[i].x][nds[i].y]=1,ans++;31 }32 if(nowy>1&&lg[nowx][nowy-1]&&!vis[nowx][nowy-1]){33 q.push(make_pair(nowx,nowy-1)); vis[nowx][nowy-1]=1;34 for(int i=g[nowx][nowy-1];i;i=nds[i].n)35 if(!lg[nds[i].x][nds[i].y])lg[nds[i].x][nds[i].y]=1,ans++;36 }37 if(nowy<n&&lg[nowx][nowy+1]&&!vis[nowx][nowy+1]){38 q.push(make_pair(nowx,nowy+1)); vis[nowx][nowy+1]=1;39 for(int i=g[nowx][nowy+1];i;i=nds[i].n)40 if(!lg[nds[i].x][nds[i].y])lg[nds[i].x][nds[i].y]=1,ans++;41 }42 }43 }44 int main(){45 n=read(); m=read();46 inc(i,1,m){47 int a=read(),b=read(),c=read(),d=read(); nds[i]=(nd){c,d,g[a][b]}; g[a][b]=i;48 }49 ans=1; lg[1][1]=1;50 while(1){int x=ans; bfs(1,1); if(ans==x)break;} printf("%d",ans); return 0;51 }
20160908
bzoj4395[Usaco2015 dec]Switching on the Lights*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。