Submission #71663766

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

int n, m;
char s[N][N];
int dis[N * N];
bool st[N * N];

int id(int i, int j) {
	return (i - 1) * m + j;
}

int id(char x) {
	return x - 'a' + 1 + n * m;
}

vector<pair<int, int>> g[N * N];

void add(int a, int b, int c) {
	g[a].emplace_back(b, c);
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i )
		for (int j = 1; j <= m; ++ j ) {
			cin >> s[i][j];
			if (s[i][j] != '.' && s[i][j] != '#') {
				add(id(i, j), id(s[i][j]), 1);
				add(id(s[i][j]), id(i, j), 0);
			}
		}
	
	for (int i = 1; i <= n; ++ i )
		for (int j = 1; j <= m; ++ j ) if (s[i][j] != '#') {
			for (int k = 0; k < 4; ++ k ) {
				int x = i + dx[k], y = j + dy[k];
				if (x >= 1 && y >= 1 && x <= n && y <= m && s[i][j] != '#') {
					add(id(i, j), id(x, y), 1);
				}
			}
		}
	
	deque<int> q;
	memset(dis, 0x3f, sizeof dis);
	dis[id(1, 1)] = 0;
	q.push_back(id(1, 1));
	while (q.size()) {
		int u = q.front();
		q.pop_front();
		
		if (st[u]) continue;
		st[u] = true;
		
		for (auto [v, w] : g[u]) {
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (w) q.push_back(v);
				else q.push_front(v);
			}
		}
	}
	
	int res = dis[id(n, m)];
	if (res > 1e9) res = -1;
	cout << res;
	
	return 0;
}

Submission Info

Judge Result