题解

问题概述

鲁滨逊的小船被困在一个 ( n \times n ) 的网格中，网格包含水域（.）、障碍物（X）和小船的部分（r）。小船只能上下左右移动，每次移动一格，且移动后小船必须完全处于水域中。目标是找到使小船完全离开网格所需的最少移动次数，如果无法实现则输出 "NIE"。

算法思路

该问题可以转化为在网格上寻找一条路径，使得小船从初始位置移动到网格边界外，且移动过程中小船始终不接触障碍物。由于小船具有对称性且中间宽两头窄，算法通过以下步骤高效求解：

1. 定位小船：

   • 扫描网格，找到小船占据的边界（最小和最大的行和列）。
   • 通过统计每行每列的小船部分数量，确定小船的中心点 ((x, y))（即小船最宽处）。

2. 建模小船形状：

   • 小船沿纵轴对称，因此对于中心点以上的每一行（向上 (dx) 步）和以下的每一行（向下 (dx) 步），计算小船在水平方向上的左右扩展距离。
   • 使用数组 (l) 和 (r) 记录从中心列 (y) 向左和向右的扩展距离。

3. 预处理障碍物影响：

   • 对于每一列，计算从每个位置向上和向下的连续水域长度。这用于判断小船能否以某个位置为中心放置而不碰到障碍物。
   • 使用差分数组 (bk) 标记小船可以安全放置的水平区间。对于每个位置 ((i, j))，如果小船可以放置，则标记区间 ([from, to])。

4. 计算边界代价：

   • 对于网格中的每个点 ((i, j))，预计算从该点移动到网格边界所需的最小代价 (cst[i][j])。考虑小船的形状和方向，计算垂直和水平移动的代价。

5. BFS 搜索最短路径：

   • 从小船中心点 ((x, y)) 开始进行 BFS，遍历所有可达点。
   • 对于每个可达点，更新答案为当前移动距离加上从该点到边界的最小代价 (cst[i][j])。
   • 如果 BFS 结束后没有找到可行路径，输出 "NIE"。

复杂度分析

• 网格大小为 (n \times n)，其中 (n \leq 2000)，因此网格最多有 (4 \times 10^6) 个点。
• BFS 和预处理步骤的时间复杂度均为 (O(n^2))，在合理范围内。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> tpi;
const int N = 2e3 + 5;
char mp[N][N];
bool vis[N][N];
int n, lx = N, ly = N, rx, ry, cnti[N], cntj[N], x, y, l[2][N], r[2][N], way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int obs[2][N], bk[N][N], cst[N][N];

void chmin(int &a, int b) {
    a = min(a, b);
}

void chmax(int &a, int b) {
    a = max(a, b);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> mp[i][j];
            if (mp[i][j] == 'r') {
                cnti[i]++, cntj[j]++;
                chmin(lx, i), chmax(rx, i);
                chmin(ly, j), chmax(ry, j);
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        if (cnti[x] < cnti[i]) x = i;
    for (int j = 1; j <= n; ++j)
        if (cntj[y] < cntj[j]) y = j;

    for (int i = lx; i <= rx; ++i) {
        int dx = x - i;
        int fl = 0;
        if (dx < 0) dx = -dx, fl = 1;
        l[fl][dx] = N;
        for (int j = ly; j <= ry; ++j) {
            if (mp[i][j] == 'r')
                chmin(l[fl][dx], j), chmax(r[fl][dx], j);
        }
        l[fl][dx] = y - l[fl][dx];
        r[fl][dx] = r[fl][dx] - y;
    }

    int len[2] = {x - lx, rx - x};
    for (int j = 1; j <= n; ++j) {
        obs[0][0] = obs[1][n + 1] = N;
        for (int i = 1; i <= n; ++i)
            obs[0][i] = (mp[i][j] == 'X' ? 0 : obs[0][i - 1] + 1);
        for (int i = n; i >= 1; --i)
            obs[1][i] = (mp[i][j] == 'X' ? 0 : obs[1][i + 1] + 1);
        for (int i = 1; i <= n; ++i) {
            int from = N, to = 0;
            for (int k : {0, 1}) {
                if (obs[k][i] <= len[k]) {
                    chmin(from, j - r[k][obs[k][i]]);
                    chmax(to, j + l[k][obs[k][i]]);
                }
            }
            chmax(from, 1), chmin(to, n);
            if (from <= to) {
                bk[i][from]++;
                bk[i][to + 1]--;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            bk[i][j] += bk[i][j - 1];
            cst[i][j] = 1e9;
            if (i == 1 && j == 1)
                for (int dx = 1; dx <= len[1]; ++dx)
                    chmin(cst[i][j], dx + r[1][dx] + 1);
            if (i == 1 && j == n)
                for (int dx = 1; dx <= len[1]; ++dx)
                    chmin(cst[i][j], dx + l[1][dx] + 1);
            if (i == n && j == 1)
                for (int dx = 1; dx <= len[0]; ++dx)
                    chmin(cst[i][j], dx + r[0][dx] + 1);
            if (i == n && j == n)
                for (int dx = 1; dx <= len[0]; ++dx)
                    chmin(cst[i][j], dx + l[0][dx] + 1);
            if (i == 1) chmin(cst[i][j], rx - x + 1);
            if (i == n) chmin(cst[i][j], x - lx + 1);
            if (j == 1) chmin(cst[i][j], ry - y + 1);
            if (j == n) chmin(cst[i][j], y - ly + 1);
        }
    }

    queue<tpi> q;
    q.push(tpi{x, y, 0});
    vis[x][y] = 1;
    int ans = 1e9;
    while (!q.empty()) {
        int x, y, dist;
        tie(x, y, dist) = q.front();
        q.pop();
        chmin(ans, dist + cst[x][y]);
        for (int k = 0; k < 4; ++k) {
            int xx = x + way[k][0], yy = y + way[k][1];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && !vis[xx][yy] && !bk[xx][yy]) {
                vis[xx][yy] = 1;
                q.push(tpi{xx, yy, dist + 1});
            }
        }
    }

    if (ans == 1e9) cout << "NIE";
    else cout << ans;
    return 0;
}

样例解释

对于样例输入：

10
..........
..........
..r.......
.rrrX.....
rrrrr.....
.rrr......
X.r.......
.Xr.......
..........
..........

小船的中心位于第5行第5列（基于代码中的1-indexed）。通过BFS和预处理，计算得到最少需要10次移动才能将小船移出网格。

该算法高效地结合了小船的形状特征和网格搜索，确保了在合理时间内解决问题。