P9272 [CEOI2013] Adritic 题解

· · 题解

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

显然，在区域 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 函数开头特判了一下，直接输出，结束程序，避免继续运行，产生错误的结果。