Problem 2253 Brave Force Story ICPC模擬国内予選2011 B

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2253

解き方

マップの大きさが-30から30では無いので注意。死亡。
あくまで、スタート位置、障害物が-30から30の間にある。

それさえ分かれば、優先度のあるBFSするだけ。

ソースコード

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

#define FOREACH(t,p,it) for(t::iterator it=p.begin();it!=p.end();++it)
#define foreach(t,p) FOREACH(t,p)
#define all(p) p.begin(),p.end()
#define REP(i,p) for(int i=0;i<p;i++)
#define rep(p) REP(i,p)
typedef pair<int,int> pos;
typedef pair<int,pair<int,int> > pp;
const int WH = 1000;
bool o[WH][WH];
bool v[WH][WH];
int size;

int main()
{
    int t,n; while(cin>>t>>n&&(t||n))
    {
        REP(i,WH) REP(t,WH) o[i][t]=v[i][t]=false;
        int x,y; REP(i,n){ cin>>x>>y; o[x+WH/2][y+WH/2]=true; }
        cin>>x>>y; // start

        set<pp,greater<pp> > states; states.insert( pp(t,pos(x,y)) );

        while( !states.empty() )
        {
            pp a = *states.begin(); states.erase(states.begin());
            x = (a.second).first;
            y = (a.second).second;

            if( o[x+WH/2][y+WH/2] ) continue;
            if( v[x+WH/2][y+WH/2] ) continue;
            v[x+WH/2][y+WH/2] = true;
            if( a.first == 0 ) continue;

            states.insert( pp(a.first-1,pos(x-1,y)) );
            states.insert( pp(a.first-1,pos(x-1,y-1)) );
            states.insert( pp(a.first-1,pos(x,y-1)) );
            states.insert( pp(a.first-1,pos(x+1,y)) );
            states.insert( pp(a.first-1,pos(x+1,y+1)) );
            states.insert( pp(a.first-1,pos(x,y+1)) );
        }

        int sum = 0;
        REP(i,WH) REP(t,WH) sum+=(v[i][t]?1:0);
        cout << sum << endl;
    }

    return 0;
}