Submission #1692127

---

Source Code Expand

#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<stack>
#include<queue>
#include<list>

#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000

using namespace std;


int main(void) {
	int r, c;
	int now;
	int place;
	queue<int> que;
	int sy, sx, gy, gx;
	int posx, posy;
	char ch[51][51];
	int dp[51][51];

	FOR(i, 0, 50) {
		FOR(t, 0, 50) {
			dp[i][t] = INF;
		}
	}
	cin >> r >> c;
	cin >> sy >> sx;
	cin >> gy >> gx;
	FOR(i, 1, r) {
		cin >> ch[i];
	}

	place = sx + (sy - 1)*c-1;
	dp[sy][sx - 1] = 0;
	que.push(place);
	while (que.empty() == 0) {
		now = que.front();
		que.pop();
		posy = now / c+1;
		posx = now - ((posy-1)*c);
		if (ch[posy][posx+1] == '.'&&dp[posy][posx+1] ==INF) {
			dp[posy][posx + 1] = dp[posy][posx]+1;
			que.push(now + 1);
		}
		if (ch[posy][posx - 1] == '.'&&dp[posy][posx - 1] == INF) {
			dp[posy][posx - 1] = dp[posy][posx] + 1;
			que.push(now - 1);
		}
		if (ch[posy + 1][posx] == '.'&&dp[posy + 1][posx] == INF) {
			dp[posy + 1][posx] = dp[posy][posx] + 1;
			que.push(now +c);
		}
		if (ch[posy - 1][posx] == '.'&&dp[posy - 1][posx] == INF) {
			dp[posy - 1][posx] = dp[posy][posx] + 1;
			que.push(now -c);
		}
	}
	cout << dp[gy][gx-1] << endl;
	return 0;
}

Submission Info

Judge Result