【AOJ 2253】Brave Force Story

問題

Brave Force Story | Aizu Online Judge

方針

• BFSをする.
• その際にそこにたどり着ける距離を保存し, 最後にたどり着けたマスの数を数える.
• 普通に探索するとインデックスが負になって悲しくなるので, 適当に座標をずらす.

コード

#include <algorithm>
#include <iostream>
#include <queue>
 
using namespace std;
 
#define INF 1<<20
#define rep(i, n) REP(i,0,n)
#define REP(i,a,n) for(int i = a; i < (int)n ; i++)
 
bool barrier[200][200];
int d[200][200];
int dx[] = {0,  0, -1, -1, 1, 1};
int dy[] = {1, -1,  0, -1, 0, 1};
 
struct NODE{
  int x_, y_, d_;
  NODE(int x, int y, int d){
    x_ = x; y_ = y; d_ = d;
  }
};
 
 
int solve(int x, int y, int turn){
  queue<NODE> que;
  que.push(NODE(x, y, 0));
   
  d[x][y] = 0;
 
  while(!que.empty()){
    NODE p = que.front(); que.pop();
     
    if(p.d_ >= turn) continue;
     
    d[p.x_][p.y_] = p.d_;
 
    rep(i, 6){
      int nx = p.x_ + dx[i]; int ny = p.y_ + dy[i];
      if(nx < 0 || 200 <= nx || ny < 0 || 200 <= ny || d[nx][ny] <= p.d_+1 || barrier[nx][ny]) continue;
      d[nx][ny] = p.d_+1;
      que.push(NODE(nx, ny, p.d_+1));
    }
  }
   
  int ans = 0;
  rep(i, 200){
    rep(j, 200){
      if(d[i][j] != INF) ans++;
    }
  }
  queue<NODE>().swap(que); 
  return ans;
}
 
signed main(){
  int t, n;
   
  while(cin >> t >> n, t || n){
    int x, y;
 
    rep(i, 200){
      rep(j, 200){
    barrier[i][j] = false;
    d[i][j] = INF;
      }
    }
 
    rep(i, n){
      cin >> x >> y;
      barrier[x+100][y+100] = true;
    }
     
    cin >> x >> y;
    cout << solve(x+100, y+100, t) << endl;
  }
   
  return 0;
}