AOJ 0122 - Summer of Phyonkichi

深さ優先探索で行けると見た．

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
typedef std::pair<int,int> P;
P wpos[10];
int n;
int dfs(int x, int y, int i){
	if(i == n)return 1;//最後まで生き残れた

	std::vector<P> flog, water;
	for(int j=-1;j<=1;j++){
		flog.push_back(P(x-2,y+j));
		flog.push_back(P(x+2,y+j));
		flog.push_back(P(x+j,y-2));
		flog.push_back(P(x+j,y+2));
	}

	for(int j=-1;j<=1;j++){
		for(int k=-1;k<=1;k++){
			water.push_back(P(wpos[i].first+k, wpos[i].second+j));
		}
	}

	for(int j=0;j<flog.size();j++){
		if(std::find(water.begin(), water.end(), flog[j]) != water.end() && flog[j].first >= 0 && flog[j].second >= 0 && flog[j].first < 10 && flog[j].second < 10){
			if(dfs(flog[j].first, flog[j].second, i+1))
				return 1;
		}
	}

	return 0;//どうあがいても絶望
}

int main(){
	int posX, posY;
	while(std::cin >> posX >> posY, posX && posY){
		std::cin >> n;
		for(int i=0;i<n;i++){
			int wposX, wposY;
			std::cin >> wposX >> wposY;
			wpos[i] = P(wposX, wposY);
		}
		
		if(dfs(posX, posY, 0))puts("OK");
		else puts("NA");
	}

	return 0;
}