题目链接
首先拆点，把每个点拆成4个点，表示到达这个点的时候赛车的朝向。
然后考虑连边。
相邻同向并且都是可以走的点直接连边权1的边。
至于怎么转向，只需在每个点\(i\)向每个方向一直拓展直到不能走为止，如果当前点的深度大于灵敏度，从\(i\)向这个点的其它3个方向都连一条边权为这个点的深度的边。
然后跑\(SPFA\)（至于为什么是\(SPFA\)，我才不会告诉你是博主懒），这样你可以获得\(90pts\)。
为什么？因为我们最多要跑\(10\)次，而每次连边的时间复杂度都是\(O(n^3)\)级别的，加上要跑\(SPFA\)，很容易超时。
所以考虑一个优化，显然每次连边有很多重复的地方，因为灵敏度为\(2\)的情况肯定也把灵敏度为\(3\)的情况的所有边都连了。
所以我们不妨反过来跑，灵敏度从\(10\)到\(1\)，每次只连长度刚好为灵敏度的转向边，用栈记录一下答案就行了。
\(90pts\)：
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#define Open(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define Close fclose(stdin); fclose(stdout);
#define O(x) cout << #x << "=" << x << endl;
using namespace std;
const int MAXN = 10010 << 2;
const int MAXM = 5000000;
struct Edge{int next, to, dis;
}e[MAXM << 1];
int head[MAXN], num, dis[MAXN], vis[MAXN], a[110][110];
inline void Add(int u, int v, int dis){e[++num] = (Edge){ head[u], v, dis }; head[u] = num;
}
int n, m, N, l[] = { -1, 1, 0, 0 }, r[] = { 0, 0, -1, 1 }, sx, sy, px, py;
inline int id(int x, int y, int direct){return direct * N + (x - 1) * m + y;
}
queue <int> q;
int work(int check){num = 0; memset(head, 0, sizeof head);memset(dis, 127, sizeof dis);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j){if(!a[i][j]) continue;for(int k = 0; k < 4; ++k){int x = i + l[k], y = j + r[k];if(!a[x][y]) continue;Add(id(i, j, k), id(x, y, k), 1);for(int o = 1; a[x][y]; x += l[k], y += r[k], ++o)if(o >= check)for(int l = 0; l < 4; ++l)if(l != k)Add(id(i, j, k), id(x, y, l), o);}}dis[id(sx, sy, 0)] = dis[id(sx, sy, 1)] = dis[id(sx, sy, 2)] = dis[id(sx, sy, 3)] = 0;vis[id(sx, sy, 0)] = vis[id(sx, sy, 1)] = vis[id(sx, sy, 2)] = vis[id(sx, sy, 3)] = 1;q.push(id(sx, sy, 0)); q.push(id(sx, sy, 1)); q.push(id(sx, sy, 2)); q.push(id(sx, sy, 3));while(q.size()){int u = q.front(); q.pop();vis[u] = 0;for(int i = head[u]; i; i = e[i].next)if(dis[e[i].to] > dis[u] + e[i].dis){dis[e[i].to] = dis[u] + e[i].dis;if(!vis[e[i].to]){vis[e[i].to] = 1;q.push(e[i].to);}}}int ans = min(min(dis[id(px, py, 0)], dis[id(px, py, 1)]), min(dis[id(px, py, 2)], dis[id(px, py, 3)]));if(ans < 10000000) return printf("%d %d\n", check, ans), 0;else return 1;
}
int main(){scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &px, &py); N = n * m;for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)scanf("%d", &a[i][j]);for(int i = 1; i <= 10; ++i)if(work(i))break;return 0;
}\(100pts\)
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#define Open(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define Close fclose(stdin); fclose(stdout);
#define O(x) cout << #x << "=" << x << endl;
using namespace std;
const int MAXN = 10010 << 2;
const int MAXM = 5000000;
struct Edge{int next, to, dis;
}e[MAXM << 1];
int head[MAXN], num, dis[MAXN], vis[MAXN], a[110][110], s[12], top;
inline void Add(int u, int v, int dis){e[++num] = (Edge){ head[u], v, dis }; head[u] = num;
}
int n, m, N, l[] = { -1, 1, 0, 0 }, r[] = { 0, 0, -1, 1 }, sx, sy, px, py;
inline int id(int x, int y, int direct){return direct * N + (x - 1) * m + y;
}
queue <int> q;
void work(int check){for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j){if(!a[i][j]) continue;for(int k = 0; k < 4; ++k){for(int p = 1, x = i + l[k], y = j + r[k]; a[x][y]; ++p, x += l[k], y += r[k])if(p == check){for(int l = 0; l < 4; ++l)if(l != k)Add(id(i, j, k), id(x, y, l), check);break;}}}memset(dis, 127, sizeof dis);dis[id(sx, sy, 0)] = dis[id(sx, sy, 1)] = dis[id(sx, sy, 2)] = dis[id(sx, sy, 3)] = 0;vis[id(sx, sy, 0)] = vis[id(sx, sy, 1)] = vis[id(sx, sy, 2)] = vis[id(sx, sy, 3)] = 1;q.push(id(sx, sy, 0)); q.push(id(sx, sy, 1)); q.push(id(sx, sy, 2)); q.push(id(sx, sy, 3));while(q.size()){int u = q.front(); q.pop();vis[u] = 0;for(int i = head[u]; i; i = e[i].next)if(dis[e[i].to] > dis[u] + e[i].dis){dis[e[i].to] = dis[u] + e[i].dis;if(!vis[e[i].to]){vis[e[i].to] = 1;q.push(e[i].to);}}}int ans = min(min(dis[id(px, py, 0)], dis[id(px, py, 1)]), min(dis[id(px, py, 2)], dis[id(px, py, 3)]));if(ans < 10000000) s[++top] = ans;
}
int main(){scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &px, &py); N = n * m;for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j)scanf("%d", &a[i][j]);for(int i = 1; i <= n; ++i)for(int j = 1; j <= m; ++j){if(!a[i][j]) continue;for(int k = 0; k < 4; ++k){int x = i + l[k], y = j + r[k];if(!a[x][y]) continue;Add(id(i, j, k), id(x, y, k), 1);}}for(int i = 10; i; --i)work(i);for(int Top = top, i = 1; i <= Top; ++i)printf("%d %d\n", i, s[top--]);return 0;
}