个人练习-PAT甲级-1091 Acute Stroke

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805375457411072

照理讲应该是BFS题，不过偷懒，多开了些数组，想直接扫描输入时就记录结果。写着写着感觉漏缺还是挺多的，但写都写了，总要写写完吧，debug了挺久，最后还是过了，记录下注意点。之后有机会再用BFS版本写一遍。

定义一个坐标的结构体

class Coord {
    
public:int x, y, z;Coord() {
    }Coord(int i, int j, int k) {
    x = i; y = j; z = k;}
};

一些数组，lump[]是记录stroke块的数组，每一个元素是一个stroke块的vector，stroke块就是空间上连续的stroke点的集合。
g[][][]存某个坐标是否为stroke点
cor2idx[]：输入坐标，得到这个坐标在lump[]数组的哪一个元素里（在哪一个stroke块里）

vector<vector<Coord>> lump;
bool g[1330][130][70];
int cor2idx[1330][130][70];
int M, N, L, T;

初始化所有cor2idx，因为开始时lump[]中什么也没有。

void Init() {
    for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
    for (int k = 0; k < L; k++)cor2idx[i][j][k] = -1;}}
}

读入数据，读入一个stroke点就将其加入lump，并给他的cor2idx赋好值。为什么可以这样呢？因为【相邻】的定义是x,y,z方向上分别+1或-1得到的6个坐标，我们每次其实只要考虑-1方向上的3个坐标即可。因为我们扫描的顺序都是x,y,z从小到大的，这样扫描完毕后每个相邻关系其实都可以被探测到。

    for (int k = 0; k < L; k++) {
    for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
    scanf("%d", &tmp);if (tmp) {
    g[i][j][k] = true;Add(i, j, k);}}}}

重要函数Add()，将stroke点加入lump，并给他的cor2idx赋好值。遍历3个低处的相邻点，如果它们中有stroke点，就将自身合并进去，然后，将自身和3个相邻点（如果是stroke点）都合并进同一个stroke块。这点非常重要，否则会出现这样的特例：
设本身为0，相邻点为1,2,3；三个相邻点都为stroke点；
0和1合并进了1号stroke块（lump[1]）；
然而2号还在2号stroke块中（lump[2]），3号还在3号stroke块中（lump[3]）；
由于0与1,2,3都是相邻的，它们本应属于同一个stroke块，所以需要把2号和3号合并进lump[1]；

换句话说，【一个点若为stroke点，它有可能会把周围的几个stroke块都合并成同一个stroke块】

反之，若三个相邻点都不是stroke点，那么本身自己成为一个stroke块。

void Add(int i, int j, int k) {
    Coord c(i, j, k);int px[3] = {
     -1, 0, 0 };int py[3] = {
     0, -1, 0 };int pz[3] = {
     0, 0, -1 };int tx, ty, tz;bool flag = false;for (int cnt = 0; cnt < 3; cnt++) {
    tx = i + px[cnt];ty = j + py[cnt];tz = k + pz[cnt];if (tx >= 0 && tx < M && ty >= 0 && ty < N && tz >= 0 && tz < L) {
    int pos = cor2idx[tx][ty][tz];if (pos != -1) {
    flag = true;lump[pos].push_back(c);cor2idx[i][j][k] = pos;break;}}}if (!flag) {
    cor2idx[i][j][k] = findEmpty();if (cor2idx[i][j][k] == lump.size()) {
    vector<Coord> vc;vc.push_back(c);lump.push_back(vc);}else lump[cor2idx[i][j][k]].push_back(c);}else{
    for (int cnt = 0; cnt < 3; cnt++) {
    tx = i + px[cnt];ty = j + py[cnt];tz = k + pz[cnt];if (tx >= 0 && tx < M && ty >= 0 && ty < N && tz >= 0 && tz < L) {
    int m_pos = cor2idx[i][j][k];int pos = cor2idx[tx][ty][tz];if (pos != -1) {
    if (pos != m_pos) {
    if (lump[pos].size() < lump[m_pos].size()) Merge(pos, m_pos);else Merge(m_pos, pos);}}}}}}

合并stroke块时我们把小的合并进大的，同时把cor2idx的值改变。并把小的stroke块位置清空（但不要删除，否则所有stroke块的编号全乱了），这个空位可以给新的stroke块使用

void Merge(int p1, int p2) {
    for (int i = 0; i < lump[p1].size(); i++) {
    lump[p2].push_back(lump[p1][i]);cor2idx[lump[p1][i].x][lump[p1][i].y][lump[p1][i].z] = p2;}lump[p1].clear();
}

为节省空间，有新的stroke块时，先找找lump[]中是否有空的位置（一次合并后会留下一个空位），有空的就用空的；没有再新开空间。

int findEmpty() {
    int ret;for (ret = 0; ret < lump.size(); ret++) {
    if (lump[ret].size() == 0)return ret;}return ret;
}

最后计算，输出即可

    int ret = 0;for (int i = 0; i < lump.size(); i++) {
    if (lump[i].size() >= T)ret += lump[i].size();}printf("%d", ret);

完整代码

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<map>
#include<set>
#include<queue>
#include<string.h>using namespace std;class Coord {
    
public:int x, y, z;Coord() {
    }Coord(int i, int j, int k) {
    x = i; y = j; z = k;}
};vector<vector<Coord>> lump;
bool g[1286][128][60];
int cor2idx[1286][128][60];
int M, N, L, T;void Init() {
    for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
    for (int k = 0; k < L; k++)cor2idx[i][j][k] = -1;}}
}int findEmpty() {
    int ret;for (ret = 0; ret < lump.size(); ret++) {
    if (lump[ret].size() == 0)return ret;}return ret;
}void Merge(int p1, int p2) {
    for (int i = 0; i < lump[p1].size(); i++) {
    lump[p2].push_back(lump[p1][i]);cor2idx[lump[p1][i].x][lump[p1][i].y][lump[p1][i].z] = p2;}lump[p1].clear();
}void Add(int i, int j, int k) {
    Coord c(i, j, k);int px[3] = {
     -1, 0, 0 };int py[3] = {
     0, -1, 0 };int pz[3] = {
     0, 0, -1 };int tx, ty, tz;bool flag = false;for (int cnt = 0; cnt < 3; cnt++) {
    tx = i + px[cnt];ty = j + py[cnt];tz = k + pz[cnt];if (tx >= 0 && tx < M && ty >= 0 && ty < N && tz >= 0 && tz < L) {
    int pos = cor2idx[tx][ty][tz];if (pos != -1) {
    flag = true;lump[pos].push_back(c);cor2idx[i][j][k] = pos;break;}}}if (!flag) {
    cor2idx[i][j][k] = findEmpty();if (cor2idx[i][j][k] == lump.size()) {
    vector<Coord> vc;vc.push_back(c);lump.push_back(vc);}else lump[cor2idx[i][j][k]].push_back(c);}else{
    for (int cnt = 0; cnt < 3; cnt++) {
    tx = i + px[cnt];ty = j + py[cnt];tz = k + pz[cnt];if (tx >= 0 && tx < M && ty >= 0 && ty < N && tz >= 0 && tz < L) {
    int m_pos = cor2idx[i][j][k];int pos = cor2idx[tx][ty][tz];if (pos != -1) {
    if (pos != m_pos) {
    if (lump[pos].size() < lump[m_pos].size()) Merge(pos, m_pos);else Merge(m_pos, pos);}}}}}}int main() {
    int tmp;scanf("%d %d %d %d", &M, &N, &L, &T);Init();for (int k = 0; k < L; k++) {
    for (int i = 0; i < M; i++) {
    for (int j = 0; j < N; j++) {
    scanf("%d", &tmp);if (tmp) {
    g[i][j][k] = true;Add(i, j, k);}}}}int ret = 0;for (int i = 0; i < lump.size(); i++) {
    if (lump[i].size() >= T)ret += lump[i].size();}printf("%d", ret);return 0;
}