Submission #11588831

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

inline int ctoi(char c) { if(c < '0' || '9' < c) throw invalid_argument("ctoi error"); return c - '0'; }
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for(int i = (int)(k); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

template <typename T>
inline T gcd(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("gcd error: x <= 0 or y <= 0");
	
	if(x < y) swap(x, y);
	T r = x % y;

	while(r != 0){
		x = y;
		y = r;
		r = x % y;
	}

	return y;
}
template <typename T>
inline T lcm(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("lcm error: x <= 0 or y <= 0");

	return x * y / gcd(x, y);
}

int h, w;
int sy, sx;
int gy, gx;

vector<vector<bool>> walk;
vector<vector<int>> step;
queue<pair<int, int>> q;

void push_bfs(int x, int y, int s){
	if(x < 0 || y < 0 || w <= x || h <= y) return;
	if(!walk[y][x] || step[y][x] != -1) return;

	q.push(make_pair(x, y));
	step[y][x] = s + 1; 
}

int main(){
	cin >> h >> w;
	cin >> sy >> sx;
	cin >> gy >> gx;
	sy--;
	sx--;
	gy--;
	gx--;

	rep(i, h){
		vector<bool> vw;
		vector<int> vs;

		rep(j, w){
			char c;
			cin >> c;

			if(c == '.'){
				vw.push_back(true);
			}
			else{
				vw.push_back(false);
			}

			vs.push_back(-1);
		
		}

		walk.push_back(vw);
		step.push_back(vs);
	}

	q.push(make_pair(sx, sy));
	step[sy][sx] = 0;

	while(!q.empty()){
		pair<int, int> p = q.front();
		int x = p.first;
		int y = p.second;
		q.pop();
		int s = step[y][x];

		push_bfs(x - 1, y, s);
		push_bfs(x + 1, y, s);
		push_bfs(x, y - 1, s);
		push_bfs(x, y + 1, s);
	}

	/*
	for(auto i : step){
		for(auto j : i){
			if(j == -1) cout << j << " ";
			else cout << " " << j << " ";
		}
		cout << endl;
	}
	*/
	
	cout << step[gy][gx] << endl;

	return 0;
}

Submission Info

Judge Result