Submission #71678351

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define debug(arg) cout << "[" << #arg << "]: " << arg << endl
#else
#define debug(arg) 42
#endif

using llu = uint64_t;
using ll = int64_t;

#define vec vector
#define pb push_back
#define all(n) begin(n), end(n)

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

void solv() {
	int n, m; cin >> n >> m;
	vec<string> mat(n); for (auto &s : mat) cin >> s;
	vec<vec<pair<int, int>>> adj(26);
	for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (mat[i][j] >= 'a') adj[mat[i][j] - 'a'].pb({i, j});
	auto good = [&](int x, int y) {return x >= 0 && x < n && y >= 0 && y < m && mat[x][y] != '#';};
	vec<vec<int>> dist(n, vec<int>(m, INT_MAX));
	vec<int> xdist(26, INT_MAX);
	deque<tuple<int, int, int>> pq;
	dist[0][0] = 0;
	pq.push_front({0, 0, 0});
	while (!pq.empty()) {
		auto [d, x, y] = pq.front();
		debug(d << ' ' << x << ' ' << y);
		pq.pop_front();
		if (x == n) {
			int c = y;
			for (auto &[x, y] : adj[c]) if (dist[x][y] > d + 1) {
				dist[x][y] = d + 1;
				pq.push_back({d + 1, x, y});
			}
		} else {
			if (int c = mat[x][y] - 'a'; c >= 0 && xdist[c] > d) {
				xdist[c] = d;
				pq.push_front({d, n, c});
			}
			for (int k = 0; k < 4; ++k) {
				int X = x + dx[k], Y = y + dy[k];
				if (!good(X, Y)) continue;
				if (dist[X][Y] > d + 1) {
					dist[X][Y] = d + 1;
					pq.push_back({d + 1, X, Y});
				}
			}
		}
	}
	cout << (dist[n - 1][m - 1] == INT_MAX ? -1 : dist[n - 1][m - 1]) << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) solv();
	return 0;
}

Submission Info

Judge Result