Submission #691527

---

Source Code Expand

/*
   迷路問題における幅優先探索
   */
#include<iostream>
#include<queue>

using namespace std;

const int MAX_M = 50;
const int MAX_N = 50;
const int INF = 10000000;

typedef pair<int, int> P;

char maze[MAX_N][MAX_M+1];
int N, M;
int sx, sy;
int gx, gy;

int d[MAX_N][MAX_M];

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int bfs();
void solve();

int main(){

  cin>>N;
  cin>>M;
  cin>>sy;
  cin>>sx;
  cin>>gy;
  cin>>gx;
  sx--;
  sy--;
  gy--;
  gx--;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
      cin>>maze[i][j];
    }
  }
  solve();
  return 0;
}

int bfs(){
  queue<P> que;
  for(int i = 0; i < N; i++)
    for(int j = 0; j < M; j++) d[i][j] = INF;
 
  que.push(P(sy, sx));
  d[sy][sx] = 0;

  while(que.size()){
    P p = que.front(); que.pop();
    if(p.first == gy && p.second == gx) break;

    for(int i = 0; i < 4; i++){
      int nx = p.first + dx[i], ny = p.second + dy[i];

      if(0 <= nx && nx < N && 0 <= ny && ny < M && maze[nx][ny] != '#' && d[nx][ny] == INF){
        que.push(P(nx, ny));
        d[nx][ny] = d[p.first][p.second] + 1;
      }
    }
  }
  return d[gy][gx];
}

void solve(){
  int res = bfs();
  cout<<res<<endl;
}

Submission Info

Judge Result