AOJ : 2253 - ブレイブ・フォース・ストーリー (Brave Force Story)

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2253
日本語の問題文なので, 説明は省略です.

アルゴリズム

次の状態を保持して, 幅優先探索しました.

• x座標
• y座標
• 歩数

座標はマイナスになることがあるので少し面倒かもしれません. コーディングを簡単にするためには, 次の２つの方法があるでしょう.

• 入力される座標全てに大きめの数字を足す方法
• 障害物の位置をmapで持っておいて, 障害物があるかどうかはこのmapを参照する
  • 座標がマイナスになっても大丈夫

プログラム

class State{
public:
  int x,y,cost;

  State(){}
  State(int _x,int _y,int _cost){
    x = _x;
    y = _y;
    cost = _cost;
  }
};

int n,m;
int sx,sy;
bool t[1000][1000];
bool closed[1000][1000];
int dx[] = {0,1,1,0,-1,-1};
int dy[] = {1,1,0,-1,-1,0};

void solve(){
  queue<State> open;
  memset(closed,0,sizeof(closed));
  open.push(State(sx,sy,0));

  int ans = 0;

  while(!open.empty()){
    State st = open.front(); open.pop();
    if(closed[st.x][st.y] || st.cost>n || t[st.y][st.x]) continue;
    closed[st.x][st.y] = true;

    ans++;

    rep(i,6){
      int nx = st.x + dx[i];
      int ny = st.y + dy[i];
      open.push(State(nx,ny,st.cost+1));
    }
  }

  cout<<ans<<endl;
}

int main(){
  while(cin>>n>>m,n||m){
    memset(t,0,sizeof(t));
    rep(i,m){
      int x,y;
      cin>>x>>y;
      x += 300;
      y += 300;
      t[y][x] = true;
    }

    cin>>sx>>sy;
    sx += 300;
    sy += 300;

    solve();
  }
}