PKU 3626 Mud Puddles
http://poj.org/problem?id=3626
最短路問題。
泥の場所を通らないで、できるだけ早く目的の場所にたどり着けみたいな問題。
やや易。
座標を変換してやりました。
int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; bool vis[1100][1100]; main(){ int x,y,n; cin>>x>>y>>n; x+=500,y+=500; rep(i,n){ int a,b; cin>>a>>b; a+=500; b+=500; vis[a][b]=1; } queue<pair<int,PI> > Q; Q.push(mp(0,mp(500,500))); while(!Q.empty()){ int cc=Q.front().F,cx=Q.front().S.F,cy=Q.front().S.S; Q.pop(); if(cx==x && cy==y){ cout<<cc<<endl; return 0; } if(vis[cx][cy])continue; vis[cx][cy]=true; rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || 1010<=nx || ny<0 || 1010<=ny || vis[nx][ny])continue; Q.push(mp(cc+1,mp(nx,ny))); } } }