Problem 0193 : Deven-Eleven

Deven-Eleven
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0193

• 問題概要

六角形のマップの上で、他のコンビニよりも近くにある土地は自分の陣地。
等距離は陣地ではない。
もうすでにたってるコンビニの座標が与えられる。
自分のコンビニを立てる候補地が与えられる。
候補地の中で確保できる陣地の最大数を求めなさい。
　

• 解法

それぞれのコンビニの座標からBFSして、その場所から一番近いコンビニまでの距離をすべての土地に記憶する。
そのあと、すべての候補地から、BFSして、記憶している距離より近い土地の数を数える。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

#define N 100

using namespace std;

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

int w, h;
bool flag;
int t[N][N];

class State{
public:
  int x, y, cost;
  State(){
    cost = 0;
  }
  bool next(int d){
    int nx = x + dx[y%2][d], ny = y + dy[d];
    if(nx < 0 || ny < 0 || nx >= w || ny >= h){
      return false;
    }
    x = nx; y = ny;
    cost++;
    return true;
  }
};

int BFS(int x, int y){
  int cnt=0;
  State s;
  s.x = x; s.y = y;
  queue<State> Q;
  Q.push(s);
  bool visited[N][N];
  
  rep(i, N)rep(j, N)visited[i][j] = false;
  while(!Q.empty()){
    State now = Q.front();
    Q.pop();
    if(visited[now.y][now.x] || t[now.y][now.x] <= now.cost)continue;
    if(flag)t[now.y][now.x] = now.cost;
    visited[now.y][now.x] = true;
    cnt++;
    rep(i, 6){
      State next = now;
      if(next.next(i))Q.push(next);
    }
  }
  return cnt;
}
main(){
  
  while(cin >> w){
    if(w == 0)break;
    cin >> h;
    rep(i, N){
      rep(j, N){
	t[i][j] = 100000000;
      }
    }

    //already store
    flag = true;
    {
      int n;
      cin >> n;
      rep(i, n){
	int x, y;
	cin >> x >> y;
	x--;y--;
	BFS(x, y);
      }
    }
    //kouho place
    flag = false;
    {
      int n, ans = 0;
      cin >> n;
      rep(i, n){
	int x, y;
	cin >> x >> y;
	x--;y--;
	ans = max(ans, BFS(x, y));
      }
	
      cout << ans << endl;
    } 
  }
}