3626 Mud Puddles

問題概要

座標平面の原点から、(x,y)まで、格子点を通り移動する。
1回の移動は座標軸に平行に、ちょうど1の距離だけ動ける。

座標平面上には、m個の泥の点があり、それらの点には移動することができない。
ゴールまで辿り着く最小の移動回数を求めよ。

• 500≦x,y≦500を満たす。

解法

泥の座標は-500から500なので、最悪でもその外側を通れば目的地に行ける。（それより外のマスを通る意味はない）

よって座標を501だけずらした後、幅優先をすればよい。

ソースコード

const int n=1003,dy[]={-1,0,1,0},dx[]={0,-1,0,1};
bool m[n][n],v[n][n];

int main(){
	int x,y,k,a,b; scanf("%d%d%d",&x,&y,&k);
	x+=501; y+=501;
	rep(i,k){
		scanf("%d%d",&a,&b);
		m[a+501][b+501]=1;
	}
	v[501][501]=1;
	queue<pair<int,int> > Q; Q.push(mp(0,501*n+501));
	while(!Q.empty()){
		int cx=Q.front().second/n,cy=Q.front().second%n,
		cc=Q.front().first; Q.pop();
		
		if(cx==x&&cy==y){
			printf("%d\n",cc); break;
		}
		
		rep(d,4){
			int nx=cx+dx[d],ny=cy+dy[d];
			if(nx<0||nx>=n||ny<0||ny>=n||v[nx][ny]||m[nx][ny])continue;
			v[nx][ny]=1; Q.push(mp(cc+1,nx*n+ny));
		}
	}
	return 0;
}