阿里云可以几个网站,去泰国做网站发网站,大连模板建站平台,深圳网络运营推广公司题目 分析 但凡是最优方案可能需要访问同一个点的情况#xff0c;都需要应用“拆点”#xff0c;或者说分层图的技巧。多出来的维度主要是区分同一个点的不同状态而用。 对于本题#xff0c;访问的时机便是一个区分点。 对于类似题“AB路线”#xff0c;同一个K段的位置是…题目 分析 但凡是最优方案可能需要访问同一个点的情况都需要应用“拆点”或者说分层图的技巧。多出来的维度主要是区分同一个点的不同状态而用。 对于本题访问的时机便是一个区分点。 对于类似题“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);queuenode 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.t1] 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.t1] u.t 1;q.push({x, y, u.t1});}}}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博客
