AOJ : 0193 - Deven-Eleven

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0193&lang=jp
日本語の問題文なので説明は省略です

アルゴリズム

各マスから, 一番近い店への最小距離を記憶するマップを, 幅優先によって求めておきます.
候補地が入力されたら, その位置から幅優先を行います.
この際, マップに記憶されている値より, 候補地からの距離の方が小さいようなマスがあれば, カウントしていきます.
このカウント値が答えです.

※今回は, Hex座標なので, 幅優先で遷移していくとき, 偶数列と奇数列では, 遷移の仕方が異なるので注意です.

プログラム

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int,int> P;
typedef pair<P,int> PP;

#define REP(i,n,m) for(int i=n;i<m;i++)
#define rep(i,n) REP(i,0,n)
#define INF 999999999

int w,h,s,t;
int d[102][102]; //各マスから一番近い店への最小距離
bool closed[102][102]; //幅優先用

int dx1[] = { 0, 1, 1, 1, 0,-1}; //奇数列からの遷移
int dy1[] = {-1,-1, 0, 1, 1, 0}; //奇数列
int dx2[] = {-1, 0, 1, 0,-1,-1}; //偶数列
int dy2[] = {-1,-1, 0, 1, 1, 0}; //偶数列

//flg : マップを塗るか塗らないか
int draw(int x,int y,bool flg){
  int res = 0;
  queue<PP> q;
  memset(closed,0,sizeof(closed));

  q.push(PP(P(x,y),0));

  while(!q.empty()){
    PP p = q.front(); q.pop();
    int x = p.first.first;
    int y = p.first.second;
    if(closed[y][x]) continue;
    closed[y][x] = true;

    if(d[y][x] > p.second){
      if(flg) d[y][x] = p.second;
      res++;
    }

    for(int i=0;i<6;i++){
      int nx = x + (y%2==1 ? dx1[i] : dx2[i]);
      int ny = y + (y%2==1 ? dy1[i] : dy2[i]);
      if(nx>=0 && nx<w && ny>=0 && ny<h){
        q.push(PP(P(nx,ny),p.second+1));
      }
    }
  }
  return res;
}

int main(void){
  while(cin>>w>>h,w){
    rep(i,h) rep(j,w) d[i][j] = INF;

    cin>>s;
    rep(i,s){
      int p,q;
      cin>>p>>q;
      draw(p-1,q-1,true);
    }

    int ans = 0;
    cin>>t;
    rep(i,t){
      int p,q;
      cin>>p>>q;
      ans = max(ans,draw(p-1,q-1,false));
    }

    cout<<ans<<endl;
  }

  return 0;
}