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