Submission #1318010

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
using namespace std;
#define INF 1<<21
#define DIV 1000000007

typedef pair<int, int> Pair;

char maze[55][55];
int d[55][55];

int N, M;
int sx, sy;
int gx, gy;

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

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

  while (!q.empty()) {
	Pair p = q.front(); q.pop();
	if (p.first == gx&&p.second == gy) 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) {
		q.push(Pair(nx, ny));
		d[nx][ny] = d[p.first][p.second] + 1;
	  }
	}
  }

  return d[gx][gy];

}

int main() {
  cin >> N >> M;
  cin >> sx >> sy;
  cin >> gx >> gy;
  for (int i = 1; i <= N; i++) {
	for (int j = 1; j <= M; j++) {
	  cin >> maze[i][j];
	}
  }
  cout << bfs() << endl;
}

Submission Info

Judge Result