NC24043. [USACO 2015 Dec S]Switching on the Lights
描述
Bessie starts in room (1,1)(1,1), the only room that is initially lit. In some rooms, she will find light switches that she can use to toggle the lights in other rooms; for example there might be a switch in room (1,1)(1,1) that toggles the lights in room (1,2)(1,2). Bessie can only travel through lit rooms, and she can only move from a room (x,y)(x,y) to its four adjacent neighbors (x−1,y)(x−1,y), (x+1,y)(x+1,y), (x,y−1)(x,y−1)and (x,y+1)(x,y+1) (or possibly fewer neighbors if this room is on the boundary of the grid).
Please determine the maximum number of rooms Bessie can illuminate.
输入描述
The first line of input contains integers NN and MM (1≤M≤20,0001≤M≤20,000).
The next MM lines each describe a single light switch with four integers xx, yy, aa, bb, that a switch in room (x,y)(x,y) can be used to toggle the lights in room (a,b)(a,b). Multiple switches may exist in any room, and multiple switches may toggle the lights of any room.
输出描述
A single line giving the maximum number of rooms Bessie can illuminate.
示例1
输入:
3 6 1 1 1 2 2 1 2 2 1 1 1 3 2 3 3 1 1 3 1 2 1 3 2 1
输出:
5
说明:
Here, Bessie can use the switch in (1,1)(1,1) to turn on lights in (1,2)(1,2) and (1,3)(1,3). She can then walk to (1,3)(1,3) and turn on the lights in(2,1)(2,1), from which she can turn on the lights in (2,2)(2,2). The switch in (2,3)(2,3) is inaccessible to her, being in an unlit room. She can therefore illuminate at most 5 rooms.C++14(g++5.4) 解法, 执行用时: 15ms, 内存消耗: 1256K, 提交时间: 2019-06-29 14:57:15
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=(b);i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#include<vector>
using namespace std;
vector<int> e[110][110];
int n,m,xx,yy,aa,bb,qx[11000],qy[11000],he,ta,nx,ny,ans;
bool g[110][110],l[110][110];
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
int main(){
scanf("%d%d",&n,&m);
fo(i,1,m){
scanf("%d%d%d%d",&xx,&yy,&aa,&bb);
e[xx][yy].push_back(aa*(n+1)+bb);
}
g[1][1]=l[1][1]=1;
qx[1]=qy[1]=1;he=ta=1;ans=1;
// return 0;
while (he<=ta){
// printf("bfs %d %d\n",qx[he],qy[he]);
fo(i,0,3){
nx=qx[he]+dx[i];
ny=qy[he]+dy[i];
if (1<=nx&&nx<=n&&1<=ny&&ny<=n){
if (!g[nx][ny]){
g[nx][ny]=1;
if (l[nx][ny]){
qx[++ta]=nx;
qy[ta]=ny;
}
}
}
}
if (e[qx[he]][qy[he]].size()) fo(i,0,e[qx[he]][qy[he]].size()-1){//!!!!!!!!!!if (e[qx[he]][qy[he]].size())
nx=e[qx[he]][qy[he]][i]/(n+1);
ny=e[qx[he]][qy[he]][i]%(n+1);
if (!l[nx][ny]){
l[nx][ny]=1;
ans++;
if (g[nx][ny]){
qx[++ta]=nx;
qy[ta]=ny;
}
}
}
he++;
}
printf("%d\n",ans);//ta
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 37ms, 内存消耗: 980K, 提交时间: 2019-06-30 19:46:13
#include<bits/stdc++.h>
using namespace std;
struct node{
int tx,ty,nt;
}a[200005];
int n,m,fir[105][105],len,b[105][105],v[105][105],c;
void dfs(int x,int y){
if (x<1||x>n||y<1||y>n)return;
v[x][y]=1;
for (int i=fir[x][y];i!=0;i=a[i].nt)
if(b[a[i].tx][a[i].ty]==0){
b[a[i].tx][a[i].ty]=1;
c++;
if(v[a[i].tx+1][a[i].ty]==1||v[a[i].tx][a[i].ty+1]==1||v[a[i].tx-1][a[i].ty]==1||v[a[i].tx][a[i].ty-1]==1)dfs(a[i].tx,a[i].ty);
}
if(v[x+1][y]==0&&b[x+1][y]==1)dfs(x+1,y);
if(v[x][y+1]==0&&b[x][y+1]==1)dfs(x,y+1);
if(v[x-1][y]==0&&b[x-1][y]==1)dfs(x-1,y);
if(v[x][y-1]==0&&b[x][y-1]==1)dfs(x,y-1);
}
int main(){
cin>>n>>m;
int fx,fy,tx,ty;
for(int i=1;i<=m;i++){
cin>>fx>>fy>>tx>>ty;
a[++len].tx=tx;
a[len].ty=ty;
a[len].nt=fir[fx][fy];
fir[fx][fy]=len;
}
b[1][1]=1;
c=1;
dfs(1,1);
cout<<c<<"\n";
return 0;
}