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