【游戏——BFS+分层图】

题目

分析 

但凡是最优方案可能需要访问同一个点的情况，都需要应用“拆点”，或者说分层图的技巧。多出来的维度主要是区分同一个点的不同状态而用。

对于本题，访问的时机便是一个区分点。

对于类似题“AB路线”，同一个K段的位置是一个区分点（不会跨越一个K段，不然不是最优）。

代码

#include <bits/stdc++.h>
using namespace std;const int N = 110;
const int M = 310;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};struct node
{int x, y, t;
};int l[N][N], r[N][N];
int dist[N][N][M];
bool st[N][N];
int n, m, t;int bfs()
{memset(dist, 0x3f, sizeof dist);queue<node> q;q.push({1, 1, 0});dist[1][1][0] = 0;while(q.size()){auto u = q.front(); q.pop();for(int i = 0; i < 4; i++){int x = u.x + dx[i];int y = u.y + dy[i];if(x < 1 || y < 1 || x > n || y > m) continue;if(dist[x][y][u.t+1] > u.t + 1 && (u.t + 1 < l[x][y] || u.t + 1 > r[x][y])){if(x == n && y == m) return u.t + 1;dist[x][y][u.t+1] = u.t + 1;q.push({x, y, u.t+1});}}}return -1;
}int main()
{scanf("%d%d%d", &n, &m, &t);for(int i = 1; i <= t; i++){int x, y, a, b;scanf("%d%d%d%d", &x, &y, &a, &b);l[x][y] = a, r[x][y] = b;}printf("%d", bfs());
}

类似题 

AB路线——BFS+分层图-CSDN博客