AOJ_0122 Summer of Phyonkichi

問題
解法
幅優先探索する。ジャンプ先の配列を用意しておくと便利。
領域外に出てしまったときの処理を書き忘れていて、すこし手間取った。

コード

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;	//座標
typedef pair<int, P>   Q;	//噴水の番号と座標
const int MAX_N = 10, MAX_HUNSUI = 10;
int map[MAX_N][MAX_N];
int hunsui_n;
P h[MAX_HUNSUI];

//ジャンプ先座標の配列
int dx[] = {-2,-2,-2, -1, 0, 1, 2, 2, 2, 1, 0,-1};
int dy[] = { 1, 0,-1, -2,-2,-2,-1, 0, 1, 2, 2, 2};

//周辺に噴水があるか
bool isHunsuiAround(int x, int y, int num){
	for(int i = -1; i <= 1; i++){
		for(int j = -1; j <= 1; j++){
	                //領域外にでてしまったときの処理
			if(x + i < 0 || MAX_N <= x + i || y + j < 0 || MAX_N <= y + j) continue;

			if(map[x + i][y + j] == num)
				return true;
		}
	}
	return false;
}
bool bfs(int px, int py){
	priority_queue<Q, vector<Q>, greater<Q> > pque;
	pque.push(Q(0, P(px, py)));
	while(!pque.empty()){
		Q q = pque.top(); pque.pop();
		if(q.first == hunsui_n) return true; //最後の噴水
		int x = q.second.first, y = q.second.second;
		//各ジャンプ先に対して
		for(int i = 0; i < 12; i++){
			int nx = x + dx[i], ny = y + dy[i];
			//周辺に噴水があるか調べる
			if(isHunsuiAround(nx, ny, q.first)){
				//噴水があったのでキューにPUSH
				pque.push(Q(q.first + 1, P(nx, ny)));
			}
		}
	}
	return false;
}
int main(){
	int px, py;
	while(scanf("%d %d", &px, &py)){
		if(px == 0 && py == 0) break;
		for(int i = 0; i < MAX_N; i++)
			for(int j = 0; j < MAX_N; j++)
				map[i][j] = -1;
		scanf("%d", &hunsui_n);
		for(int i = 0; i < hunsui_n; i++){
			scanf("%d %d", &h[i].first, &h[i].second);
			map[h[i].first][h[i].second] = i;
		}
		if(bfs(px, py)){
			printf("OK\n");
		}else{
			printf("NA\n");
		}
	}
	return 0;
}