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;

}