zPatronus's blog

luoguP2845 [USACO15DEC]Switching on the Lights 开关灯

Posted on Edited on

题目

函数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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}

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