先贴我的代码。

dijkstra + heap 最大一点跑了 146ms。rec.

我觉得这是正解。如果不是，欢迎指正。

时限可以开到 250ms，或者更大。

#include <bits/stdc++.h>

using namespace std;

const int N = 555;

int n, m, k;
struct node {
	int to, w;
};
set <pair <int, int> > q;
vector <node> e[N * N];
char a[N][N];
int dist[N * N];

int leftup(int x, int y) {return (x - 1) * (m + 1) + y;}
int leftdown(int x, int y) {return leftup(x, y) + m + 1;}
int rightup(int x, int y) {return leftup(x, y) + 1;}
int rightdown(int x, int y) {return leftdown(x, y) + 1;}

void dijkstra(int S, int E) {
	q.clear();
	memset(dist, 127, sizeof(dist));
	dist[S] = 0;
	for (int i = 1; i <= k; i++) q.insert({dist[i], i});
	for (; !q.empty(); ) {
		int x = q.begin()->second;
		if (dist[x] > 1 << 30 || x == E) break;
		q.erase(q.begin());
		for (auto i : e[x]) 
			if (dist[i.to] > dist[x] + i.w) {
				q.erase({dist[i.to], i.to});
				dist[i.to] = dist[x] + i.w;
				q.insert({dist[i.to], i.to});
			}
	}
	if (dist[E] < 1 << 30) printf("%d", dist[E]);
	else printf("NO SOLUTION");
}

int main() {
	scanf("%d%d", &n, &m);
	k = (n + 1) * (m + 1);
	for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) {
			int _1 = leftup(i, j);
			int _2 = leftdown(i, j);
			int _3 = rightup(i, j);
			int _4 = rightdown(i, j);
			e[_1].push_back({_4, (a[i][j] == '/')});
			e[_4].push_back({_1, (a[i][j] == '/')});
			e[_2].push_back({_3, (a[i][j] != '/')});
			e[_3].push_back({_2, (a[i][j] != '/')});
		}
	dijkstra(1, k);
	return 0;
}