翻译
一个n*m的二进制矩阵，上下左右的1联通算一块区域，问有多少个区域。
输入行数 n，和列数 m(1 ≤ n ≤ 10244, 4 ≤ m ≤ 102416)，题目保证m可以被4整除 ，输入 n 行，m/4 列的16进制数字，可得一个 m*n 的二进制矩阵(一位16进制数字可以转成4位二进制数字)，上下左右连着的1算是一块，问这个二进制矩阵一共有多少块。
样例讲解
3 4
1
A
B
可以转成
0001
1010
1011
很明显, 有三块
Note that the memory limit is unusual!
注意这道题目的有特殊的内存限制
分析
简化的题目就是一个矩阵有多少 1 的连着的集合，分析出考的是 并查集。而难点是内存限制为 16 megabytes，计算一下数据如果把输入的16进制数字都存储起来需要的内存是 1024*4*1024*4 = 16MB，而把转成2进制的矩阵存起来需要的内存是 1024*4*1024*16 = 64MB，已经大于内存的限制。
所以需要一行一行的输入并且计算，重复使用这个数组。这个思路叫做滚动数组，主要用于优化空间复杂度，节约内存的占用。
每行计算时，需要注意连通判定需要与上一行和当前行进行比较，所以需要两个数组，分别存储上一行和当前行。因为重复使用数组的缘故，需要每次把并查集的根转移到当前行，这样才可以把根传递下去，保证正确。
每读一行16进制数据，都直接放入转成二进制数据。
先判断当前位置和左边是否是连着的1，如果是则尝试合并，并且把左边的根改成当前位置。再尝试与上一行的合并，并且把上一行的根设置成当前位置。这样就可以把根一直传递下来，保证所有的根都在当前行。
答案就是，1的个数 - 合并次数
例子
3 4
A
A
A
转成
1010
1010
1010
坐标系：左上角是(0, 0), 左下角是(2, 0), 右下角是(2, 2)
计算第一行，根分别是自己：
(0, 0), (0, 1), (0, 2), (0, 3)
计算第二行，根存了两行：
(1, 0), (0, 1), (1, 2), (0, 3)
(1, 0), (1, 1), (1, 2), (1, 3)
计算第三行:
(2, 0), (0, 1), (2, 2), (0, 3)
(2, 0), (2, 1), (2, 2), (2, 3)
代码(C++)
//
// main.cpp
// ACM
//
// Created by Tconan on 2017/11/8.
// Copyright © 2017年 Tconan. All rights reserved.
//
#include <iostream>
#include <stdio.h>
using namespace std;
// 创建这个类是为了更好的理解，会比数组直观
class Point {
public:
Point *parent;
};
// 获取当前位置的根
Point* get(Point* point) {
if (point->parent != point) {
// 优化数据结构，直接把自己的根直接指向获取到的根
point->parent = get(point->parent);
return point->parent;
}
return point;
}
// 尝试合并两个位置，如果本属于两个结合，则把右边的根的根指向左边的，也就是合并两个集合
int merge(Point* left, Point* right) {
left = get(left);
right = get(right);
if (left == right) {
return 0;
}
right->parent = left;
return 1;
}
int value[1024*16];
int lastValue[1024*16];
char s[1024*16];
Point *root;
Point *lastRoot;
int main(int argc, const char * argv[]) {
int n, m, sum = 0;
cin>>n>>m;
for (int row=0; row<n; ++row) {
// 读取数据，转成2进制
scanf("%s", s);
for (int index=0; index<m/4; ++index) {
char c = s[index];
if (c >= 'A') {
c = c - 'A' + '9' + 1;
}
value[index*4+0] = (c&8)>0?1:0;
value[index*4+1] = (c&4)>0?1:0;
value[index*4+2] = (c&2)>0?1:0;
value[index*4+3] = (c&1)>0?1:0;
}
root = new Point[1024*16];
for (int index=0; index<m; ++index) {
root[index].parent = &root[index];
if (value[index] == 0) {
continue;
}
sum ++;
// 尝试与左边合并
if (index > 0 && value[index-1] == 1) {
sum -= merge(&root[index-1], &root[index]);
}
// 尝试与上边合并
if (row > 0 && lastValue[index] == 1) {
sum -= merge(&root[index], &lastRoot[index]);
}
}
// 数组滚动，把当前行的值给上一行，下次循环会新读取并计算当前行数据
for (int index=0; index<m; ++index) {
lastValue[index] = value[index];
}
// 滚动数组，存储根
delete []lastRoot;
lastRoot = root;
}
cout<<sum<<endl;
return 0;
}
我程序的 Accepted 截图
吐槽
这道题 Codeforces 给各个语言的运行时间都是3S，可是这个数据量下，Python2 空 for 循环就需要近2S的时间，基本不可能完成这个题目的。Codeforces 上也大都用C++完成这道题目的，少部分人用了 Java 或 Kotlin 。
Accepted 使用的语言截图
最开始我用了 Python2 写这道题目，完善程序逻辑之后遇见了超时，自测极限数据，需要40S+的运行时间。
Python的超时
遂放弃用 Python2 AC，转用C++完成这道题目。C++效率还是蛮高的，但最后还是改用scanf才通过了测试，我看有人用cin通过测试，佩服这些人写的程序，同样的算法，常数比我低。但我还是更喜欢可读性比较高的代码，方便阅读与理解。
网友评论