题目分析

我们需要找到最大的颜色数量，使得朋友无法发现传送门的存在。关键观察是：

1. 如果朋友可能认为他两次访问了同一个单元格，但实际上访问的是不同的传送门，那么这两个传送门必须同色
2. 朋友的运动路径可以表示为坐标的线性组合
3. 核心问题转化为：找出所有必须同色的传送门集合

关键思路

经过数学推导，我们发现：

• 对于任意两个传送门 $(x_i, y_i)$ 和 $(x_j, y_j)$，如果存在整数 $a, b$ 使得：$$x_i + a = x_j, \quad y_i + b = y_j$$ 且 $a$ 和 $b$ 的奇偶性满足某些条件，那么这两个传送门必须同色
• 实际上，这等价于：如果两个传送门的坐标差 $(dx, dy) = (x_j - x_i, y_j - y_i)$ 满足：$$dx \equiv 0 \pmod{2} \quad \text{且} \quad dy \equiv 0 \pmod{2} $$那么它们可能需要在同一个连通分量中

算法步骤

1. 特殊情况处理：如果只有一个传送门，输出 -1
2. 构建并查集：用于合并必须同色的传送门
3. 坐标变换：将所有坐标平移到非负范围
4. 按奇偶性分组：根据坐标的奇偶性建立连接关系
5. 统计连通分量：最终答案就是连通分量的数量

C 语言实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_N 100005

typedef struct {
    int x, y;
    int id;
} Point;

int parent[MAX_N];
int rank[MAX_N];

// 并查集 - 查找
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

// 并查集 - 合并
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    
    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else if (rank[x] > rank[y]) {
        parent[y] = x;
    } else {
        parent[y] = x;
        rank[x]++;
    }
}

// 比较函数 - 按x坐标排序
int compare_x(const void *a, const void *b) {
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;
    if (p1->x != p2->x) return p1->x - p2->x;
    return p1->y - p2->y;
}

// 比较函数 - 按y坐标排序
int compare_y(const void *a, const void *b) {
    Point *p1 = (Point *)a;
    Point *p2 = (Point *)b;
    if (p1->y != p2->y) return p1->y - p2->y;
    return p1->x - p2->x;
}

int main() {
    int n;
    scanf("%d", &n);
    
    Point points[MAX_N];
    
    // 读取所有传送门坐标
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &points[i].x, &points[i].y);
        points[i].id = i;
        parent[i] = i;
        rank[i] = 0;
    }
    
    // 特殊情况：只有一个传送门
    if (n == 1) {
        printf("-1\n");
        return 0;
    }
    
    // 方法1：按x坐标排序，连接相邻的相同x坐标且y坐标差为偶数的点
    qsort(points, n, sizeof(Point), compare_x);
    
    for (int i = 0; i < n; i++) {
        int j = i + 1;
        // 寻找相同x坐标的点
        while (j < n && points[j].x == points[i].x) {
            // 如果y坐标差是偶数，则需要同色
            if ((points[j].y - points[i].y) % 2 == 0) {
                unite(points[i].id, points[j].id);
            }
            j++;
        }
    }
    
    // 方法2：按y坐标排序，连接相邻的相同y坐标且x坐标差为偶数的点
    qsort(points, n, sizeof(Point), compare_y);
    
    for (int i = 0; i < n; i++) {
        int j = i + 1;
        // 寻找相同y坐标的点
        while (j < n && points[j].y == points[i].y) {
            // 如果x坐标差是偶数，则需要同色
            if ((points[j].x - points[i].x) % 2 == 0) {
                unite(points[i].id, points[j].id);
            }
            j++;
        }
    }
    
    // 方法3：连接所有坐标差都是偶数的点（在2x2的网格中）
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dx = abs(points[i].x - points[j].x);
            int dy = abs(points[i].y - points[j].y);
            if (dx % 2 == 0 && dy % 2 == 0) {
                unite(points[i].id, points[j].id);
            }
        }
    }
    
    // 统计连通分量数量
    int component_count = 0;
    bool visited[MAX_N] = {false};
    
    for (int i = 0; i < n; i++) {
        int root = find(i);
        if (!visited[root]) {
            visited[root] = true;
            component_count++;
        }
    }
    
    printf("%d\n", component_count);
    return 0;
}

算法优化

上面的基础版本在 n 较大时可能较慢，这里提供一个优化版本：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_N 100005
#define OFFSET 1000000  // 坐标偏移量

typedef struct {
    int x, y, id;
} Point;

int parent[MAX_N];
int rank[MAX_N];

// 哈希表节点
typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

Node* hash_table[2 * OFFSET + 5] = {NULL};

// 哈希函数
int hash(int x) {
    return x + OFFSET;
}

// 哈希表插入
void hash_insert(int key, int value) {
    int idx = hash(key);
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = key;
    new_node->value = value;
    new_node->next = hash_table[idx];
    hash_table[idx] = new_node;
}

// 哈希表查找
int hash_find(int key) {
    int idx = hash(key);
    Node* curr = hash_table[idx];
    while (curr != NULL) {
        if (curr->key == key) {
            return curr->value;
        }
        curr = curr->next;
    }
    return -1;
}

// 并查集函数
int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    
    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else if (rank[x] > rank[y]) {
        parent[y] = x;
    } else {
        parent[y] = x;
        rank[x]++;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    Point points[MAX_N];
    
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &points[i].x, &points[i].y);
        points[i].id = i;
        parent[i] = i;
        rank[i] = 0;
    }
    
    if (n == 1) {
        printf("-1\n");
        return 0;
    }
    
    // 使用哈希表优化连接过程