AOJ 0122 Summer of Phyonkichi

404 Not Found

ピョン吉の夏。パソコン甲子園2005過去問。

とりあえず実装方法誤ると大変なことになることが予想される探索でした。探索だったら何でもいいと思う。

WA出しまくった。原因は

• 上限が10固定だと思って定数指定してた
• nコ目(最後の撒水機)から1に飛べないとOK判定出せないものだと思ってた

などなど。モジュール化的なものは大切だとおもいました。まる。check関数引数一つでいいよな・・・と思った僕であった・・・。

cppソース

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

const int dx[]={ 0, 0, 1, 1,-1,-1, 2,-2,-2, 2,-2, 2};
const int dy[]={ 2,-2, 2,-2, 2,-2, 0, 0, 1, 1,-1,-1};

const int sx[]={ 0, 1,-1, 0, 0, 1, 1,-1,-1};
const int sy[]={ 0, 0, 0, 1,-1, 1,-1, 1,-1};

class NODE{
public:
	int x;
	int y;
	int pos;
};

bool check(int x,int y){
	return (x>=0 && x<10 && y>=0 && y<10);
}

int main(){
	int x,y,n,a,b;
	NODE q,qt;
	vector<int> t;
	while(cin >> x >> y && (x || y) ){
		bool flag = false;
		vector<int> all[10][10];
		cin >> n;
		rep(i,n){
			cin >> a >> b;
			rep(j,9){
				if(check(a+sx[j],b+sy[j]))
					all[a+sx[j]][b+sy[j]].push_back(i+1);
			}
		}
		queue<NODE> Q;
		q.x=x;q.y=y;
		q.pos=0;
		Q.push(q);
		while(Q.size()){
			q = Q.front();Q.pop();
			if(q.pos == n){
				if(n)flag = true; // if(n)なのは撒水機が0コのケース対策して。実際与えられてるか分からないけど。
			}
			rep(i,12){
				if(check(q.x+dx[i],q.y+dy[i])){
					t = all[q.x+dx[i]][q.y+dy[i]];
					if(count(t.begin(),t.end(),q.pos+1)){
						qt.x = q.x+dx[i];
						qt.y = q.y+dy[i];
						qt.pos = q.pos+1;
						Q.push(qt);
					}
				}
			}
		}
		cout << (flag?"OK":"NA") << endl;
	}
}