当前位置：首页 > article >正文

【游戏——BFS+分层图】

article 2025/2/25 16:13:25

题目

分析

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

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

对于类似题“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());
}