自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:46:55，当前版本为作者最后更新于2023-04-28 00:15:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，可以等效地把题目看成从目标岛屿出发到达每个其他岛屿，这在思考上更容易一些。

显然，在区域 $1$ 和 $3$ 的地方可以一次去到。

与第一张图相比，代表区域 $2$ 的矩形已经收缩了，区域 $4$ 也是如此。随着 BFS 进展到第 $3,4$ 或者更多步，这两个矩形将继续缩小，直到进行到第 $i$ 步时，没有任何岛屿在其中（所有岛屿都能在 $i$ 步以内去到）。如果我们需要知道，在 BFS 的下一步，这两个白色区域将如何缩小，只要知道在它周围最靠边的岛屿就可以了。这些岛屿在下图中用浅灰色标记。

设 $\operatorname{dp(r,c)}$ 为访问矩形 $(r,c)-(N,1)$（就是上面的空白部分）中岛屿所需的余下跳数，设 $\operatorname{cnt(r,c)}$ 为矩形中的岛屿数量。

如果矩形中没有岛屿（$\operatorname{cnt(r,c)}=0$），那么 $\operatorname{dp(r,c)}=0$，表示不需要再继续跳了。否则，当 BFS 继续，矩形会缩小至 $(\operatorname{min_r{(r,c)}},\operatorname{max_c{(r,c)}})-(N,1)$。其中 $\operatorname{min_r}$ 是矩形左侧所有岛屿中的最小行，$\operatorname{max_c}$ 是矩形下方所有岛屿中的最大列。现在，$\operatorname{dp(r,c)}$ 很容易状态转移为 $\operatorname{cnt(r,c)}+\operatorname{dp(min_r{(r,c)},max_c{(r,c)})}$。

对于左下角矩形，也用类似的方法，最后把结果加起来，就可以得到从起始岛屿开始的总跳数。

官方题解代码：

// CEOI 2013 - Task: Adriatic - Solution
// Author: Gustav Matula

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

#define MAXC 2500
#define MAXN 250005
#define CFF 0102

int N;
int x[MAXN], y[MAXN];

int on[MAXC+2][MAXC+2];
int cnt[MAXC+2][MAXC+2];
int minx[MAXC+2][MAXC+2];
int miny[MAXC+2][MAXC+2];
int maxx[MAXC+2][MAXC+2];
int maxy[MAXC+2][MAXC+2];

int mur[MAXC+2][MAXC+2];
int mdl[MAXC+2][MAXC+2];

int ur(int x, int y) {
  int &ref = mur[x][y];
  if (ref != -1) return ref;
  if (cnt[x][MAXC] - cnt[x][y-1] == 0) return ref =  0;
  return ref = cnt[x][MAXC] - cnt[x][y-1] + ur(min(x, minx[x][y-1]), max(y, maxy[x+1][y]));
}

int dl(int x, int y) {
  int &ref = mdl[x][y];
  if (ref != -1) return ref;
  if (cnt[MAXC][y] - cnt[x-1][y] == 0) return ref =  0;
  return ref = cnt[MAXC][y] - cnt[x-1][y] + dl(max(x, maxx[x][y+1]), min(y, miny[x-1][y]));
}

int main(void)
{
  scanf("%d", &N);
  
  if (N == 1) std::cout << 0, exit(0);

  for (int i = 0; i < N; ++i) {
    scanf("%d%d", x+i, y+i);
    on[x[i]][y[i]] = 1;
  }

  memset(minx, 0x3f, sizeof minx);
  memset(miny, 0x3f, sizeof miny);

  for (int i = 1; i <= MAXC; ++i) {
    for (int j = 1; j <= MAXC; ++j) {
      cnt[i][j] = on[i][j] + cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1];
      minx[i][j] = on[i][j] ? min(i, minx[i-1][j]) : min(minx[i-1][j], minx[i][j-1]);
      miny[i][j] = on[i][j] ? min(j, miny[i][j-1]) : min(miny[i-1][j], miny[i][j-1]);
    }
  }

  for (int i = MAXC; i >= 1; --i) {
    for (int j = MAXC; j >= 1; --j) {
      maxx[i][j] = on[i][j] ? max(i, maxx[i+1][j]) : max(maxx[i+1][j], maxx[i][j+1]);
      maxy[i][j] = on[i][j] ? max(j, maxy[i][j+1]) : max(maxy[i+1][j], maxy[i][j+1]);
    }
  }

  memset(mur, -1, sizeof mur);
  memset(mdl, -1, sizeof mdl);

  for (int i = 0; i < N; ++i) 
    printf("%d\n", cnt[MAXC][MAXC] + ur(x[i], y[i]) + dl(x[i], y[i]) - 3);

  return 0;
}

这题还有一个小坑点。看到说明提示最后一行，发现 $N$ 可以为 $1$，这说明什么？尝试一下，$N=1$ 时，很明显应该输出的是 $0$。所以这份代码在 main 函数开头特判了一下，直接输出，结束程序，避免继续运行，产生错误的结果。