PKU 2212 Cavern

PKU

http://poj.org/problem?id=2212

3次元の洞窟に上から水を吸い出す。
水がある座標が与えられるので、てっぺんから辿れる全ての水を吸い出すといくら吸い出せるかを答えろというような問題。

ただの幅優先。最初appとvisをset の配列で持ってたら流石にTLEしました。
なんでこんなに解いている人が少ないのか謎です。

bool app[100][100][100];
bool vis[100][100][100];

void solve(){
  int x,y,z;
  cin>>x>>y>>z;
  memset(app,0,sizeof(app));
  memset(vis,0,sizeof(vis));
  queue<pair<int,PI> > q;  
  rep(i,z){
    int p;
    cin>>p;
    rep(j,p){
      int x,y;
      cin>>x>>y;
      --x,--y;
      app[x][y][i]=true;
      if(!i) q.push(mp(i,mp(x,y)));
    }
  }
  int ans=0;
  int dx[]={1,-1,0,0,0,0},dy[]={0,0,1,-1,0,0},dz[]={0,0,0,0,1,-1};
  while(!q.empty()){
    int cz=q.front().F;
    int cx=q.front().S.F;
    int cy=q.front().S.S;
    q.pop();
    if(vis[cx][cy][cz]) continue;
    vis[cx][cy][cz]=true;
    ++ans;
    rep(i,6){
      int nx=cx+dx[i],ny=cy+dy[i],nz=cz+dz[i];
      if(min(nx,min(ny,nz))<0 ||
         nx>=x || ny>=y || nz>=z) continue;
      if(!app[nx][ny][nz]) continue;

      q.push(mp(nz,mp(nx,ny)));
    }
  }
  printf("Je nutne vycerpat %d litru vody.\n",ans*1000);
}

main(){
  ios::sync_with_stdio(false);
  int t;
  cin>>t;
  rep(i,t)
    solve();
}