AOJ_2253

この前作ったハニカムのやつを少し変えて、あとは幅優先探索する。
いま探索しているところが何ターン目のところなのかを記憶しながら探索していく。

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> D; //ターン数、位置情報
const int MAX_XY = 100 * 2;
const int C = 100; //真ん中
int dx[6] = {0, 1, 1, 0, -1, -1};
int dy[6] = {1, 1, 0, -1, -1, 0};
int hex[MAX_XY][MAX_XY];
int T, n; //ターン数上限、障害物の数
int sx, sy; //スタート地点

int solve(){
	priority_queue<D, vector<D>, greater<D> > pque;
	//スタート地点をキューにいれる準備
	int m = 1; //いけるマスの数
	D s;
	s.first = 1;
	s.second.first = sx; s.second.second = sy;
	hex[sx][sy] = 2;
	pque.push(s);
	while(!pque.empty()){
		D d = pque.top(); pque.pop();
		if(d.first > T)
			break;
		int ox = d.second.first, oy = d.second.second;
		for(int i = 0; i < 6; i++){
			if(hex[ox + dx[i]][oy + dy[i]] == 0){
				hex[ox + dx[i]][oy + dy[i]] = 2;
				m++;
				pque.push(D(d.first + 1, P(ox + dx[i], oy + dy[i])));
			}
		}
	}
	return m;
}
int main(){
	while(scanf("%d %d", &T, &n)){
		if(T == 0) return 0;
		for(int i = 0; i < MAX_XY; i++){
			for(int j = 0; j < MAX_XY; j++){
				hex[i][j] = 0;
			}
		}
		for(int i = 0; i < n; i++){
			int x, y;
			scanf("%d %d", &x, &y);
			hex[x + C][y + C] = 1;
		}
		scanf("%d %d", &sx, &sy);
		sx += C; sy += C;
		printf("%d\n", solve());
	}
	return 0;
}