会津大学オンラインジャッジ 問122

Summer of Phyonkichi
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122

カエルのぴょんきちが夏を乗り切れるかをこたえる問題。
動的計画法で十分です。



#include<stdio.h>
#include<set>
#include<stdlib.h>

struct S{
int x,y;
bool operator<(const S& s)const{
if(x!=s.x)return x<s.x;
return y<s.y;
}
};

void search(int x,int y){
S s1;
s1.x=x;
s1.y=y;
std::set<S> sets[2];
sets[0].insert(s1);
int n;
scanf("%d",&n);
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 sx,sy,now,next;
for(int i=0;i<n;i++){
scanf("%d %d",&sx,&sy);
now =i%2;
next=(i+1)%2;
for(std::set<S>::iterator it=sets[now].begin();it!=sets[now].end();it++){
s1=(*it);
for(int j=0;j<12;j++){
s1.x+=dx[j];
s1.y+=dy[j];
if(0<=s1.x||s1.x<=9||0<=s1.y||s1.y<=9){
if(abs(sx-s1.x)<=1&&abs(sy-s1.y)<=1){
sets[next].insert(s1);
}
}
s1.x-=dx[j];
s1.y-=dy[j];
}
}
sets[now].clear();
}
printf("%s\n",sets[next].empty()==false?"OK":"NA");
}

int main(){
int x,y;
while(scanf("%d %d",&x,&y)!=EOF){
if(x==0&&y==0)break;
search(x,y);
}
}