P14469 [COCI 2025/2026 #1] 皇后 / Kraljica 略解

· · 题解

思路

如果直接按照题意模拟，每个点最多走一次，每次的扩展时间为 O(n)，时间复杂度是 O(n^3) 级别的。

由于点数固定为 n ^ 2，无法优化，考虑优化扩展过程：如果此时的点 u 被扩展出的方向和待扩展的点 v 的扩展方向相同，相当于代价为 0，否则代价为 1。另外传送门的代价也为 0，所以我们可以记录横纵坐标和当前点被那个方向扩展，使用 01 BFS 可以很完美的解决这个问题，不会的可以看 P4554 小明的游戏。另外还有一个小细节，起点和传送门出口是没有方向的，可以将方向设为 0。

Code

//# pragma GCC optimize("Ofast")
# include <bits/stdc++.h>
# define fr front
# define il inline
# define fir first
# define sec second
# define vec vector
# define it iterator
# define pb push_back
# define lb lower_bound
# define ub upper_bound
# define all(x) x.begin(), x.end()
# define mem(a, b) memset(a, b, sizeof(a))

# define lc (t[p].l)
# define rc (t[p].r)
# define ls(x) (x << 1)
# define rs(x) (x << 1 | 1)
# define lson ls(p), l, mid
# define rson rs(p), mid + 1, r

# define sqr(x) ((x) * (x))
# define bpc __builtin_popcount
# define lowbit(x) ((x) & (-(x)))
# define geti(x, i) (((x) >> (i)) & 1)
# define set1(x, i) ((x) | (1 << (i)))
# define set0(x, i) ((x) & (~(1 << (i))))

# define debug1(x) cerr << #x << " = " << x << " "
# define debug2(x) cerr << #x << " = " << x << "\n"
# define bug cerr << "--------------------------\n"

# define each1(i, x) for(auto (i) : (x))
# define each2(i, x) for(auto (&i) : (x))
# define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
# define pre(i, a, b) for(int i = (a); i >= (b); -- i)
# define G(i, h, u, ne) for(int i = (h[(u)]); i; i = (ne[(i)]))
# define reps(i, a, b, c) for(int i = (a); i <= (b); i += (c))
# define pres(i, a, b, c) for(int i = (a); i >= (b); i -= (c))
using namespace std;

using DB = double;
using LL = long long;
using LDB = long double;
using PII = pair<int, int>;
using ULL = unsigned long long;

const int N = 1e3 + 10;
const int INF1 = 0x3f3f3f3f, INF2 = INT_MAX;
const LL INF3 = (LL)1e18, INF4 = 0x3f3f3f3f3f3f3f3f, INF5 = LLONG_MAX;

int n, m, sx, sy, ex, ey, ans;
int vis[N][N][10];

char mp[N][N];

vec<PII> a[10];

int dx[10] = {0, 1, 1, 1, 0, 0, -1, -1, -1};
int dy[10] = {0, -1, 0, 1, -1, 1, -1, 0, 1};

struct node{
    int x, y, dir;
};

void calc(int num, int &x, int &y){//求出编号为num的传送门的相应出口 
    each2(tmp, a[num]){
        if(tmp.fir ^ x || tmp.sec ^ y){
            x = tmp.fir, y = tmp.sec;
            return;
        }
    }
}

void BFS(){
    mem(vis, 0x3f);
    rep(i, 0, 8) vis[sx][sy][i] = 0;
    deque<node> q;
    q.pb({sx, sy, 0});//起点没有方向 

    while(!q.empty()){
        int x = q.fr().x, y = q.fr().y, dir = q.fr().dir;
        q.pop_front();

        rep(i, 1, 8){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
            if(mp[nx][ny] == '#' || vis[nx][ny][i] <= vis[x][y][dir] + (dir != i)) continue;
            vis[nx][ny][i] = vis[x][y][dir] + (dir != i);
            if(dir ^ i) q.pb({nx, ny, i});
            else q.push_front({nx, ny, i});
        }

        if('1' <= mp[x][y] && mp[x][y] <= '9'){//传送门 
            int num = mp[x][y] - '0';
            int i = x, j = y;
            calc(num, i, j);
            if(vis[i][j][0] ^ INF1) continue;
            vis[i][j][0] = vis[x][y][dir];
            q.push_front({i, j, 0});//传送门出口方向设为0 
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    ans = INF1;
    cin >> n >> m;

    rep(i, 1, n) cin >> mp[i] + 1;

    rep(i, 1, n){
        rep(j, 1, m){
            if(mp[i][j] == 'S') sx = i, sy = j;
            else if(mp[i][j] == 'E') ex = i, ey = j;
            else if(mp[i][j] != '#' && mp[i][j] != '.') a[mp[i][j] - '0'].pb({i, j});
        }
    }

    BFS();

    rep(i, 0, 8) ans = min(ans, vis[ex][ey][i]);

    if(ans ^ INF1) cout << ans;
    else cout << "-1";

    return 0;
}

我睜開雙眼，看著空白，忘記妳對我的期待，讀完了依賴，我很快就離開…………