POJ 3626 Mud Puddles

問題文
http://poj.org/problem?id=3626

解法：幅優先探索やるだけ。
感想：JOI予選にでてもおかしくない。

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int,int> P;
const int t = 510;
const int INF = 100000;
int x,y,n,ans;
int d[1020][1020];
int da[] = {0,1,0,-1};
int db[] = {1,0,-1,0};

int main(){
	cin >> x >> y >> n;
	x += t,y += t;
	for(int i = 0;i <= 1005;i++){
		for(int j = 0;j <= 1005;j++){
			d[i][j] = INF;
		}
	}
	while(n--){
		int a,b;
		cin >> a >> b;
		a += t,b += t;
		d[a][b] = -1;
	}
	queue<P> que;

	que.push(P(t,t));
	d[t][t] = 0;
	while(que.size()){
		P p = que.front(); que.pop();
		int a = p.first,b = p.second;
		for(int i = 0;i < 4;i++){
			int na = a + da[i];
			int nb = b + db[i];
			if(na >= -500+t && na <= 500+t && nb >= -500+t && nb <= 500+t && d[na][nb] == INF){
				d[na][nb] = d[a][b]+1;
				if(na == x && nb == y){
					ans = d[na][nb];
					goto out;
				}
				que.push(P(na,nb));
			}
		}
	}
	out:
	;
	cout << ans << endl;
	return 0;
}