Submission #691220

---

Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
  
#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define INF_LL 9223372036854775
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double 

using namespace std;

#define MAX_N 50

int R, C;
int sy, sx;
int gy, gx;
char maze[MAX_N][MAX_N];

void input(){

  cin >> R >> C;
  cin >> sy >> sx;
  cin >> gy >> gx;

  sx--; sy--;
  gy--; gx--;

  for(int i = 0; i < R; i++){
    for(int j = 0; j < C; j++){
      cin >> maze[i][j];
    }
  }

}

int used[MAX_N][MAX_N];

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

int solve(){

  typedef pair<int, int> II;
  queue<II> que;
  que.push(II(sx, sy));
  memset(used, -1, sizeof(used));
  used[sy][sx] = 0;

  while(que.size()){
    
    II p = que.front();
    que.pop();

    int x = p.first;
    int y = p.second;
    if(x == gx && y == gy)
      return used[y][x];

    for(int d = 0; d < 4; d++){
      int nx = x + dx[d];
      int ny = y + dy[d];
      if(0 <= nx && nx < C &&
	 0 <= ny && ny < R &&
	 maze[ny][nx] == '.'){
	if(used[ny][nx] == -1){
	  used[ny][nx] = used[y][x] + 1;
	  que.push(II(nx, ny));
	}
      }
    }

  }

  return -1;

}

int main(){

  input();

  cout << solve() << endl;

  return 0;

}

Submission Info

Judge Result