AOJ : 0122 - Summer of Phyonkichi

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0122
問題文が日本語なので, 省略です.
ただし, 以下のことに注意.

生き残れるかどうか判定するわけだから, 噴水 1〜n を永遠に無限ループで回れないといけないと考えてしまいがちです.
しかし, ここではそのような判定法ではなく, 噴水 n まで到達できただけで, 生き残れたと判定しなければいけません.

アルゴリズム

始点から, 噴水1の範囲を通って, 噴水nまで到達できるか, 幅優先で探索しました.
この問題文, 勘違いしてしまうから, 修正してほしい...
かなりWrongAnswer出しました.

プログラム

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

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

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

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

int dx[] = {-2,-2,-2,-1,-1,0,0,1,1,2,2,2};
int dy[] = {-1,0,1,-2,2,-2,2,-2,2,-1,0,1};

int main(void){
  int sx,sy;

  while(cin>>sx>>sy && (sx||sy)){
    int n;
    cin>>n;

    bool t[10][10][10];
    memset(t,0,sizeof(t));
    rep(i,n){
      int x,y;
      cin>>x>>y;
      REP(j,-1,2) REP(k,-1,2) {
        int nx = x + j;
        int ny = y + k;
        if(nx>=0 && nx<10 && ny>=0 && ny<10) t[i][ny][nx] = true;
      }
    }

    queue<State> open;
    open.push(State(-1,sx,sy));
    bool ans = false;

    if(n == 0){
      cout<<"NA\n";
      continue;
    }

    while(!open.empty()){
      State st = open.front(); open.pop();

      if(st.cost == n-1){
        ans = true;
        break;
      }

      rep(i,12){
        int nx = st.x + dx[i];
        int ny = st.y + dy[i];
        int nc = st.cost + 1;

        if(nx>=0 && nx<10 && ny>=0 && ny<10 && t[nc][ny][nx]){
          open.push(State(nc,nx,ny));
          t[nc][ny][nx] = false;
        }
      }
    }
    cout<<(ans?"OK":"NA")<<endl;
  }

  return 0;
}