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