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; }