Submission #4231414

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std ;
typedef pair<int,int> P ;

const int INF = 100000000;
int H , W ;
int sx , sy ;
int gx , gy ;
int board[60][60] ;
int nul[60][60] ;
int dx[4] = {-1,1,0,0} , dy[4] = {0,0,-1,1} ;

int bfs(){
  for(int i = 0 ; i < H ; i++ )
    for(int j = 0 ; j < W ; j++)
      nul[i][j] = INF ;
  queue<P> que ;
  que.push(P(sx-1,sy-1)) ;
  nul[sx-1][sy-1] = 0 ;
  
  while(que.size()){
    P p = que.front() ; que.pop() ;
    if(p.first == gx-1 && p.second == gy-1 ) break;
    
    for(int i = 0 ; i < 4 ; i++ ){
      int nx = p.first + dx[i] , ny = p.second + dy[i] ;
      if( nx >= 0 && ny >= 0 && nx < H && ny < W && board[nx][ny] == 0 && nul[nx][ny] == INF  ){
        que.push(P(nx,ny)) ;
        nul[nx][ny] = nul[p.first][p.second] + 1 ;
      }
    }
  }
  
  return nul[gx-1][gy-1] ;
}

int main () {
  //入力
  cin >> H >> W ;
  cin >> sx >> sy >> gx >> gy ;
  char a ;
  for(int i = 0 ; i < H ; i++ ){
    for(int j = 0 ; j < W ; j++ ){
      cin >> a ;
      if(a=='#') board[i][j] = 1 ;
      else board[i][j] = 0 ;
    }
  }
  
  //処理部
  int ans = bfs() ;
  cout << ans << endl ;
}

Submission Info

Judge Result