PKU 3626-Mud Puddles
問題概要
格子状のマス目があり、いくつかに障害物がおかれている。(0,0)から(x,y)への移動の最短距離を求めよ3
解法
BFS
実装(C++)
#include <algorithm> #include <iostream> #include <queue> #include <cstring> using namespace std; typedef pair<int,int> P; queue<P> que; int MAP[1010][1010]; int cost[1010][1010]; int d[4]={1,0,-1,0}; int main(){ int x,y,n; cin>>x>>y>>n; x+=505;y+=505; for(int i=0;i<n;i++){ int tx,ty; cin>>tx>>ty; tx+=505; ty+=505; MAP[tx][ty]=1; } que.push(P(505,505)); memset(cost,0x7f,sizeof(cost)); cost[505][505]=0; while(!que.empty()){ P now=que.front();que.pop(); int turn=cost[now.first][now.second]; if(now.first==x&&now.second==y)break; for(int i=0;i<4;i++){ int nx=now.first+d[i],ny=now.second+d[i^1]; if(MAP[nx][ny])continue; if(nx>0&&nx<1009&&ny>0&&ny<1009){ if(cost[nx][ny]>turn+1){ que.push(P(nx,ny)); cost[nx][ny]=turn+1; } } } } cout<<cost[x][y]<<endl; }