题目链接
首先拆点，把每个点拆成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
", 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
", i, s[top--]);
return 0;
}