luoguP2845 [USACO15DEC]Switching on the Lights 开关灯

Date: Mon 05 November 2018
Updated: Mon 05 November 2018

In 5. OI.

Tags: OI

题目


函数1:用于点亮(x,y)能开的灯,假设能开(xx,yy),将(xx,yy)交至函数2

函数2:判断(x,y)是否能被走到(即4个方向有被访问到的点相邻),如果能,将(x,y)交至函数1,遍历(x,y)的4个方向,如果有亮着灯但没有被访问的点(xx,yy),将(xx,yy)交至函数2

主程序:(1,1) --> 函数1


code
#include<bits/stdc++.h>
#define N 110
#define M 200010
#define mem(a,b) memset(a,b,sizeof(a))
#define fsb(a,b,c) for(int a=b;a<=(c);a++)
#define fbs(a,b,c) for(int a=b;a>=(c);a--)
using namespace std;
struct edge{
 int x,y,nt;
}a[M];
int n,m,x,y,xx,yy,cnt=0,head[N][N],li[N][N],vi[N][N],ans=1;
const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
template<typename qw>inline void rll(qw &x){
 qw f=1;x=0;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
inline void add(int x,int y,int xx,int yy){
 a[++cnt]=(edge){xx,yy,head[x][y]};head[x][y]=cnt;
}
inline void dfs(int x,int y);
inline void dfs2(int x,int y){
 int flag=0;
 fsb(i,0,3)if(vi[x+dx[i]][y+dy[i]])flag=1;
 if(flag==0)return;
 vi[x][y]=1;
 dfs(x,y);
 fsb(i,0,3){
  int xx=x+dx[i],yy=y+dy[i];
  if((!vi[xx][yy])&&(li[xx][yy]))dfs2(xx,yy);
 }
}
inline void dfs(int x,int y){
// printf("%10d %d\n",x,y);
 for(int t=head[x][y];t!=-1;t=a[t].nt){
  int xx=a[t].x,yy=a[t].y;
  if(li[xx][yy])continue;
  li[xx][yy]=1;ans++;dfs2(xx,yy);
 }
}
int main(){
// freopen("2845_1.in","r",stdin);
 rll(n);rll(m);mem(head,255);
 fsb(i,1,m){
  rll(x);rll(y);rll(xx);rll(yy);
  add(x,y,xx,yy);
 }
 mem(li,0);mem(vi,0);li[1][1]=vi[1][1]=1;
 dfs(1,1);
 printf("%d\n",ans);
 return 0;
}

注意:答案问的是开灯数而非访问数。

Social