AOJ0122

問題:Summer of Phyonkichi
時間差で動作するスプリンクラーの下をカエルのぴょん吉が渡る問題。
生死が掛かっているにも関わらず、ジャンプすることを強いられている。

#include<vector>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
#define debug(a) cout << #a << ":" << a << endl;
#define rep(i,n) for( int i=0;i<n;++i )
typedef vector< pair< int,int > > vp;
bool valid( pair<int,int> a )
{
	return( a.first >= 0 && a.second >= 0 &&
		a.first <= 9 && a.second <= 9 );
}
int main()
{
	int x,y,n;
	while( cin >> x >> y, x|y)
	{
		cin >> n;
		vp sp(n);
		rep(i,n)cin >> sp[i].first >> sp[i].second;
		
		vp a,b;
		a.push_back( make_pair(x,y) );
		rep(i,n)
		{
			b=a;
			a.clear();
			
			vp sps;
			x = sp[i].first;
			y = sp[i].second;
			for( int dx = -1; dx <= 1; ++ dx )
			for( int dy = -1; dy <= 1; ++ dy )
			{
				if( valid( make_pair( x+dx , y+dy ) ) )
					sps.push_back( make_pair( x+dx , y+dy ) );
			}

			vp ks;
			rep(j,b.size())
			{
				x = b[j].first;
				y = b[j].second;
				vp buf;
				// buf.push_back( make_pair( x,y ) ); 強いられています

				for( int dx = -2; dx <= 2; dx+=4 )
				for( int dy = -1; dy <= 1; ++ dy )
				{
					buf.push_back( make_pair( x+dx , y+dy ) );
					buf.push_back( make_pair( x+dy , y+dx ) );
				}

				rep(k,buf.size())
				{
					if( valid( buf[k] ) )
						ks.push_back( buf[k] );
				}
			}
			sort(ks.begin(),ks.end());
			sort(sps.begin(),sps.end());
			set_intersection( ks.begin(),ks.end(), sps.begin(),sps.end() ,inserter( a,a.begin() ) );
		}
		cout<< ( a.empty() ? "NA" : "OK" ) << endl;
	}
}