AOJ 2287 Water Clock

G : 水時計
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2287

問題概要

同じ大きさの立方体の箱が座標に配置されていて、
一部は繋がっていたりする。
どこかから水を流す。
それぞれおかれている高さは異なっていて、
水があふれると、隣り合う箱が高さが高いものがあった場合はそちらには溢れない。
箱がないor自分より低い位置に箱があるときは流れる。
溢れる量／流れることができる場所の量の水が流れる。
時間と場所が指定されるので、
その場所の水槽の水の高さを求めよ。

解法

シミュレーション
まず、箱の関係をグラフにする。
時間ごとに流すのではなく、
流すべき箱にすべての水を流してしまってから、そこから
配るという実装をした。（ループがないので。

ソース

#include<iostream>
#include<vector>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;
const int N = 10;

const int dx[] = {0, 1, 0, -1},
  dy[] = {-1, 0, 1, 0};

int height[N][N], color[N][N];
int H, W, numC;
double sourceFlow;
pair<int, int> beginPos;
vector<pair<int, int> >  toFlow[N*N];
double capa[N*N], volume[N*N], area[N*N];
const double C = 30.0 * 30 * 30;
const double A = 30.0 * 30.0;

void init(){
  rep(i, N)rep(j, N)color[i][j] = -1;
  numC = 0;
  rep(i, N*N){
    toFlow[i].clear();
    capa[i] = 0;
    volume[i] = 0;
    area[i] = 0;
  }
}

void reset(){
  rep(i, N*N)volume[i] = 0;
}

bool input(){
  cin >> W >> H;
  if(W + H == 0)return false;
  init();
  cin >> beginPos.second >> beginPos.first >> sourceFlow;
  rep(i, H){
    rep(j, W){
      cin >> height[i][j];
    }
  }
  return true;
}

bool validPos(int y, int x){
  if(y < 0 || x < 0 || y >= H || x >= W)return false;
  return true;
}

void putColor(int y, int x, int c){
  if(height == 0)return;
  color[y][x] = c;
  capa[c]+= C;
  area[c] += A;
  
  rep(i, 4){
    int nx = dx[i] + x, ny = dy[i] + y;
    pair<int, int> nextPos(ny, nx);
    if(!validPos(ny, nx)){
      toFlow[c].push_back(nextPos);
      continue;
    }
    if(height[ny][nx] > height[y][x])continue;
    if(height[ny][nx] < height[y][x]){
     toFlow[c].push_back(nextPos);
     continue;
    }
    if(color[ny][nx] != -1)continue;
    putColor(ny, nx, c);
  }
}

void beginColor(){
  rep(i, H){
    rep(j, W){
      if(color[i][j] != -1 || height[i][j] == 0)continue;
      putColor(i, j, numC);
      numC++;
    }
  }
}

void Flow(int y, int x, double v){
  int myColor = color[y][x];  
  if(myColor == -1)return;
  volume[myColor] += v;
  if(volume[myColor] < capa[myColor])return;
  double remain = volume[myColor] - capa[myColor];
  volume[myColor] = capa[myColor];
  FOR(it, toFlow[myColor]){
    if(!validPos(it->first, it->second))continue;
    Flow(it->first, it->second, remain / (double)toFlow[myColor].size());
  }
}

double getHeight(int y, int x){
  int myColor = color[y][x];
  return volume[myColor] / area[myColor];
}

int main(){
  while(input()){
    beginColor();
    int n;
    cin >> n;
    rep(i, n){
      int time, y, x;
      cin >> time >> x >> y;
      reset();
      Flow(beginPos.first, beginPos.second, sourceFlow * (double)time);
      cout <<(int)getHeight(y, x) << endl;
    }
  }
  return 0;
}