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