题意分析

本题要求判断一个由三维空间格点构成的序列是否能正确构成多立方体（polycube），即每个新立方体（除第一个外）必须与已存在的立方体至少有一个面贴合（共享一个单位面），且所有立方体坐标唯一。若构成正确，计算其表面积；若错误，输出第一个违规立方体的索引（从1开始）。

关键规则：

1. 合法性检查：

   • 第一个立方体必须为 (0,0,0)。
   • 从第二个立方体开始，每个新立方体必须与已存在的至少一个立方体共享一个面（即坐标差恰好一个维度为±1，其余为0）。
   • 所有坐标必须唯一，不能重复。

2. 表面积计算：
   每个立方体的6个面中，若相邻位置（上下、左右、前后）存在其他立方体，则该面不贡献表面积；否则贡献1。总表面积为所有立方体的外露面数之和。

解题思路

1. 合法性检查步骤

• 存储已存在的坐标：使用集合（Set）存储已添加的立方体坐标，确保唯一性。
• 逐个验证每个立方体：
  • 第一个立方体必须是 (0,0,0)，否则直接判定非法。
  • 对于第 i 个立方体（i≥2），检查其与已存在的所有立方体的坐标差，判断是否存在恰好一个维度差为±1，其余为0的情况（即面相邻）。若不存在，则记录当前索引 i 为违规点。

2. 表面积计算步骤

• 遍历每个立方体：对每个立方体的6个方向（±x, ±y, ±z）检查是否存在相邻立方体。
• 统计外露面数：每个方向若无相邻立方体，则表面积加1。所有立方体的外露面数总和即为总表面积。

实现步骤

1. 输入处理

• 解析每个数据集的坐标序列，注意每行可能包含多个坐标，以空格分隔，每个坐标以逗号分隔三维数值。
• 将坐标转换为元组 (x, y, z) 存储，并检查第一个坐标是否为 (0,0,0)，否则直接判定非法（索引1违规）。

2. 合法性验证

• 使用集合 points 记录已存在的坐标，初始加入第一个坐标。
• 从第二个坐标开始，遍历每个坐标 (x, y, z)，检查是否与 points 中任意坐标满足面相邻条件（即 Δx² + Δy² + Δz² = 1）。
• 若存在重复坐标或无面相邻，则记录违规索引，终止验证。

3. 表面积计算（仅当合法时执行）

• 对每个坐标 (x, y, z)，检查6个方向的相邻坐标是否在 points 中。
• 每个方向若不存在相邻坐标，则表面积加1。累加所有立方体的结果即为总表面积。

示例分析

输入数据1：

5
0,0,0 0,0,1 0,0,2 0,0,3 0,0,4

• 合法性验证：每个新立方体均与前一个共享y轴方向的面（如 (0,0,1) 与 (0,0,0) 在y维度差1），合法。
• 表面积计算：
  • 第一个和最后一个立方体各有5个外露面（仅一个相邻面）。
  • 中间三个立方体各有4个外露面（两个相邻面）。
  • 总表面积：2×5 + 3×4 = 10 + 12 = 22，与输出一致。

输入数据3：

4
0,0,0 0,0,1 1,1,0 1,1,1

• 合法性验证：第三个坐标 (1,1,0) 与前两个坐标 (0,0,0) 和 (0,0,1) 的坐标差均为 √2（非面相邻），违规索引为3，输出 NO 3。

代码实现要点

1. 坐标解析：使用字符串分割和转换，将输入的 "x,y,z" 格式转换为整数元组。
2. 面相邻判断：通过计算坐标差的平方和是否为1，快速判断是否面相邻。
3. 效率优化：在合法性验证中，对每个新坐标只需检查是否存在至少一个相邻坐标，无需遍历所有已存在坐标（可提前终止循环）。
4. 错误处理：提前处理第一个坐标非 (0,0,0) 的情况，以及重复坐标的情况。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>   
#include <map>
#include <string>  
#include <climits> 
#include <set>
#include <string> 
#include <sstream>
#include <utility>
#include <ctime>
 
using std::priority_queue;
using std::vector;
using std::swap;
using std::stack;
using std::sort;
using std::max;
using std::min;
using std::pair;
using std::map;
using std::string;
using std::cin;
using std::cout;
using std::set;
using std::queue;
using std::string;
using std::istringstream;
using std::make_pair;
using std::greater;
 
int move_x[6] = {-1, 0, 1, 0, 0, 0};
int move_y[6] = {0, -1, 0, 1, 0, 0};
int move_z[6] = {0, 0, 0, 0, -1, 1};
 
struct NODE
{
	int x, y, z;
	friend bool operator <(const NODE &op1, const NODE &op2)
	{
		if(op1.x == op2.x)
		{
			if(op1.y == op2.y)
				return op1.z < op2.z;
			return op1.y < op2.y;
		}
		return op1.x < op2.x;
	}
};
 
set<NODE> st;
 
int main()
{
	int n_case(0), T;
	scanf("%d", &T);
	while(T--)
	{
		int n;
		scanf("%d", &n);
		int ans = n*3;
		int flag = -1;
		NODE t1, t2;
		st.clear();
		scanf("%d,%d,%d", &t1.x, &t1.y, &t1.z);
		st.insert(t1);
		for(int i = 2; i <= n; ++i)
		{
			scanf("%d,%d,%d", &t1.x, &t1.y, &t1.z);
			if(flag == -1 && st.find(t1) != st.end())
				flag = i;
			if(flag == -1)
			{
				int count = 0;
				for(int j = 0; j < 6; ++j)
				{
					t2 = t1;
					t2.x += move_x[j];
					t2.y += move_y[j];
					t2.z += move_z[j];
					if(st.find(t2) != st.end())
						++count;
				}
				if(count)
					ans -= count;
				else
					flag = i;
				st.insert(t1);
			}
		}
		if(flag != -1)
			printf("%d NO %d\n", ++n_case, flag);
		else
			printf("%d %d\n", ++n_case, ans*2);
	}
	return 0;
}