AOJ 2253 Brave Force Story

ブレイブ・フォース・ストーリー
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2253

問題概要

六角座標に幾つか障害物がある。
あるスタート地点からある手数で到達できるマスの数を数えよ。

解法

BFS.
DFSの誘惑を振り切れるかどうか。
座標の管理がめんどくさかったら、計算量に余裕があるので、setにいれてしまうのも手。

ソース

#include<iostream>
#include<set>
#include<queue>

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

using namespace std;

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

set<pair<int, int> > S;

class State{
public:
  int y, x,cost;
  bool next(int d){
    if(cost == 0 )return false;
    cost--;
    y += dy[d];
    x += dx[d];
    pair<int, int> p = make_pair(y, x);
    if(S.find(p) == S.end()){
      S.insert(p);
      return true;
    }
    return false;
  }
};

int main(){
  int t, n;
  while(cin >> t >> n){
    if(t == 0 && n == 0)break;
    S.clear();
    int sy, sx;
    rep(i, n){
      int ty, tx;
      cin >> tx >> ty;
      S.insert(make_pair(ty, tx));
    }
    cin >> sx >> sy;
    S.insert(make_pair(sy, sx));
    queue<State> Q;
    for(Q.push((State){sy, sx, t}); !Q.empty();Q.pop()){
      State now = Q.front();
      rep(i, 6){
        State next = now;
        if(next.next(i)){
          Q.push(next);
        }
      }
    }
    cout << S.size() - n << endl;
  }
  return 0;
}