提出 #64540865

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1087;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
char g[N][N];
int n, m;
vector<pair<int,int>> h[N*N];
const int inf = N * N;
int dist[N * N];
int id(int x, int y) {
	return x * m + y;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> g[i];
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; ++j) {
			int u = id(i, j);
			if (g[i][j] == '.') {
				for (int k = 0; k < 4; ++k) {
					int x = i + dx[k];
					int y = j + dy[k];
					int v = id(x, y);
					if (min(x, y) < 0 || x >= n || y >= m)
						continue;
					if (g[x][y] == '.') {
						h[u].emplace_back(0, v);
					} 
				}
			} else {
				for (int k = 0; k < 4; ++k) {
					for (int s = 1; s <= 2; ++s) {
						int x = i + dx[k] * s;
						int y = j + dy[k] * s;
						int v = id(x, y);
						if (min(x, y) < 0 || x >= n || y >= m)
							continue;
						if (g[x][y] == '.') {
							h[v].emplace_back(1, u);
							h[u].emplace_back(s - 1, v);
						} else {
							h[u].emplace_back(1, v);
						}
					}
				}
			}
		}
	}
	--a, --b, --c, --d;
	int s = id(a, b);
	int t = id(c, d);
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	fill_n(dist, n * m, inf);
	dist[s] = 0;
	pq.emplace(0, s);
	while (pq.size()) {
		int w, u;
		tie(w, u) = pq.top();
		pq.pop();
		if (w != dist[u])
			continue;
		for (auto [x, v] : h[u]) {
			int nw = w + x;
			if (nw < dist[v]) {
				dist[v] = nw;
				pq.emplace(nw, v);
			}
		}
	}
	cout << dist[t] << '\n';
}

提出情報

ジャッジ結果