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

L_J_R · 2025-11-27 16:46:20 · 题解

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

思路

很容易想到 BFS，特殊点在于有 8 个方向，且每个方向要跑到边界或障碍物，遇到走过的格子（即 vis_{i,j} = 1）也不要 break！continue 就行了，具体见代码 49 行。

代码如下↓

#include<bits/stdc++.h>
using namespace std;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, -1, 1, -1, 1};

int n, m, ans = 0x3f3f3f3f;
char c[1005][1005];
struct node
{
    int x, y, cnt;
}; queue<node> q;
bool vis[1005][1005];
vector<node> v[10];

bool chk(int x, int y)
{
    if(x > n || y > m || x < 1 || y < 1) return false;
    if(c[x][y] == '#') return false;
    return true;
}

int main()
{
    cin >> n >> m; cin.get();
    for(int i = 1; i <= n; i++) 
    {
        scanf("%s", c[i] + 1);
        for(int j = 1; j <= m; j++)
        {
            if(c[i][j] == 'S') q.push({i, j, 0}), vis[i][j] = true;
            if(c[i][j] >= '0' && c[i][j] <= '9')
                v[(c[i][j] - '0')].push_back({i, j, -1});
        }
    }
    while(!q.empty())
    {
        node u = q.front(); q.pop();
        if(c[u.x][u.y] == 'E')
        {
            ans = min(ans, u.cnt);
            break;
        }
        for(int i = 0; i < 8; i++)
        {
            int t = 1;
            while(true)
            {
                int nx = u.x + t * dx[i], ny = u.y + t * dy[i]; t++;
                if(vis[nx][ny]) continue; if(!chk(nx, ny)) break;
                vis[nx][ny] = true; q.push({nx, ny, u.cnt + 1});
                if(c[nx][ny] >= '1' && c[nx][ny] <= '9')
                {
                    int tmp = c[nx][ny] - '0';
                    for(auto k : v[tmp])
                        if(k.x != nx || k.y != ny)
                        {
                            if(vis[k.x][k.y]) continue;
                            q.push({k.x, k.y, u.cnt + 1});
                            vis[k.x][k.y] = true;
                        }
                }
            }
        }
    }
    if(ans != 0x3f3f3f3f) cout << ans << endl;
    else cout << -1 << endl;
    return 0;
}