#P3908. minecraft

    ID: 3111 传统题 1000ms 256MiB 尝试: 26 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-有限候选集缩减离散化子集 DP子掩码递推 (s-1)&maskDijkstra

minecraft

题目描述

小 A 最近在玩 mc,由于挖到的矿物太少,他用奇怪的方法找到了附近 n 个 矿物的位置。现在他要你求出为了挖到这些矿物,最少需要挖开的方块个数。 一个矿物可以看成网格图上的一个单位正方形。小 A 可以选择挖开一个方格 作为开始位置,每次选择挖开一个与已经挖开的某个方格连通的方格。小 A 的目 标就是挖开所有矿物对应的方格。

输入格式

第一行一个整数 n,表示矿物个数。 接下来 n 行,每行两个整数 x和y,表示矿物左上角的坐标。

输出格式

一行一个整数,表示最少需要挖开的方块个数。

4 
0 0 
3 0 
0 2 
3 2
8

提示

N<=10,0<=x,y<10^9,

题目来源

没有写明来源