ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2253 Brave Force Story

概要


問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2253


解法


幅優先探索(BFS)で解くことができます。

この問題でひとつ注意しないといけないことがあります。
問題文には「いずれの座標も絶対値が30以下である」と書いていますが、これは(恐らく)入力で与えられる座標のことのみについてであって、六角形のフィールドの話をしているわけではありません。
ですから(30,30)からスタートして(31,30)に行くことも可能ということになります。
そこだけ注意して、大きめに配列を取っておけばきっと解けると思います。

下のコードはさすがに配列を大きく取りすぎですが、大体100x100程度の配列をとっておけば十分でしょう。


ソースコード

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

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

static const int INF = (1 << 29);
static const int dx[] = {-1,-1,0,0,1,1};
static const int dy[] = {-1,0,-1,1,0,1};

struct State{
  int x,y;
  int turn;
  
  State(){}
  State(int _x, int _y, int _turn):x(_x),y(_y),turn(_turn){}
};

int t,n;
int sx,sy;
int minCost[601][601];
bool block[601][601];

int solve(){
  queue<State> q;
  q.push(State(sx, sy, 0));
  
  rep(i,601) rep(j,601) minCost[i][j] = INF;
  minCost[sx][sy] = 0;
  
  while(!q.empty()){
    State stt = q.front();
    q.pop();
    
    stt.turn++;
    
    if(stt.turn > t) continue;
    
    rep(k,6){
      int nx = stt.x + dx[k];
      int ny = stt.y + dy[k];
      
      if(0 <= nx && nx <= 600 && 0 <= ny && ny <= 600){
        if(minCost[nx][ny] <= stt.turn) continue;
        if(block[nx][ny]) continue;
        minCost[nx][ny] = stt.turn;
        q.push(State(nx, ny, stt.turn));
      }
    }
  }

  int ans = 0;
  rep(i,601) rep(j,601) if(minCost[i][j] != INF) ans++;

  return ans;
}

int main(){
  while(cin >> t >> n && (t | n)){
    memset(block, false, sizeof(block));
    
    rep(i,n){
      int x,y;
      cin >> x >> y;
      x += 300;
      y += 300;
      block[x][y] = true;
    }
    
    cin >> sx >> sy;
    sx += 300;
    sy += 300;
    
    cout << solve() << endl;
  }
  return 0;
}