https://www.luogu.com.cn/problem/T612325
10组就够了.
要求:有三组数据规模等于题目上线.
给解决方案+赞.
原本用来早数据的代码有问题:
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
using namespace std;
// 检查信标等级的函数（实际题目解答中的核心逻辑）
int check_beacon_level(vector<vector<string>>& grid, int x, int y, int z, int n, int m, int h)
{
int max_level = 0;
for(int level = 1; level <= 5; ++level)
{
if(z - level < 0) break; // 超出底部边界
int s = 2 * level + 1;
int x1 = max(0, x - level);
int y1 = max(0, y - level);
int x2 = min(n - 1, x + level);
int y2 = min(m - 1, y + level);
// 检查是否形成完整的正方形
if(x2 - x1 + 1 != s || y2 - y1 + 1 != s) break;
bool valid = true;
for(int i = x1; i <= x2; ++i)
{
for(int j = y1; j <= y2; ++j)
{
if(grid[z - level][i][j] != '#')
{
valid = false;
break;
}
}
if(!valid) break;
}
if(valid) max_level = level;
else break;
}
return max_level;
}
// 生成随机测试用例
void generateTestCase(int n, int m, int h, int numBeacons, double density, ofstream& inputFile, ofstream& outputFile)
{
// 初始化网格为空气
vector<vector<string>> grid(h, vector<string>(n, string(m, '.')));
// 随机放置铁块
for(int z = 0; z < h; z++)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if((double)rand() / RAND_MAX < density)
{
grid[z][i][j] = '#';
}
}
}
}
// 随机放置信标
vector<pair<pair<int, int>, int>> beacons;
while(beacons.size() < numBeacons)
{
int x = rand() % n;
int y = rand() % m;
int z = rand() % h;
if(grid[z][x][y] == '.')
{
grid[z][x][y] = '@';
beacons.push_back({{x, y}, z});
}
}
// 手动添加一些确保激活的信标
if(n >= 3 && m >= 3 && h >= 2)
{
// 添加一个1级信标
int x = n / 2;
int y = m / 2;
int z = h - 1;
if(grid[z][x][y] == '.')
{
grid[z][x][y] = '@';
beacons.push_back({{x, y}, z});
// 设置底座
for(int i = max(0, x-1); i <= min(n-1, x+1); i++)
{
for(int j = max(0, y-1); j <= min(m-1, y+1); j++)
{
grid[z-1][i][j] = '#';
}
}
}
// 如果空间足够，添加一个5级信标
if(n >= 11 && m >= 11 && h >= 6)
{
int x = n / 2;
int y = m / 2;
int z = h - 1;
if(grid[z][x][y] == '.')
{
grid[z][x][y] = '@';
beacons.push_back({{x, y}, z});
// 设置5层底座
for(int level = 1; level <= 5; level++)
{
int s = 2 * level + 1;
int x1 = max(0, x - level);
int y1 = max(0, y - level);
int x2 = min(n - 1, x + level);
int y2 = min(m - 1, y + level);
for(int i = x1; i <= x2; i++)
{
for(int j = y1; j <= y2; j++)
{
grid[z - level][i][j] = '#';
}
}
}
}
}
}
// 写入输入文件
inputFile << n << " " << m << " " << h << endl;
for(int z = 0; z < h; z++)
{
for(int i = 0; i < n; i++)
{
inputFile << grid[z][i] << endl;
}
}
// 计算并写入输出文件
vector<pair<pair<int, int>, pair<int, int>>> activatedBeacons;
for(auto& b : beacons)
{
int x = b.first.first;
int y = b.first.second;
int z = b.second;
if(z == 0) continue; // 信标在最底层，无法激活
int level = check_beacon_level(grid, x, y, z, n, m, h);
if(level > 0)
{
activatedBeacons.push_back({{x+1, y+1}, {z+1, level}}); // 转为1-based坐标
}
}
outputFile << activatedBeacons.size() << endl;
for(auto& b : activatedBeacons)
{
outputFile << b.first.first << " " << b.first.second << " "
<< b.second.first << " " << b.second.second << endl;
}
}
int main()
{
srand(time(0));
// 生成20组测试用例
for(int i = 1; i <= 20; i++)
{
string inputFileName = "test" + to_string(i) + ".in";
string outputFileName = "test" + to_string(i) + ".out";
ofstream inputFile(inputFileName);
ofstream outputFile(outputFileName);
if(!inputFile.is_open() || !outputFile.is_open())
{
cerr << "无法打开文件" << endl;
return 1;
}
int n, m, h;
int numBeacons;
double density;
// 前17组为小规模测试用例
if(i <= 17)
{
n = rand() % 20 + 3; // 3-22
m = rand() % 20 + 3;
h = rand() % 10 + 2; // 2-11
numBeacons = rand() % 10 + 1; // 1-10
density = (double)(rand() % 50 + 20) / 100.0; // 0.2-0.7
}
// 最后3组为接近上限的测试用例
else
{
n = 500;
m = 500;
h = 500;
numBeacons = 50; // 大型测试用例中信标数量适中
density = 0.1; // 稀疏布局，避免生成过大的文件
}
cout << "生成测试用例 " << i << " (n=" << n << ", m=" << m << ", h=" << h << ")..." << endl;
generateTestCase(n, m, h, numBeacons, density, inputFile, outputFile);
inputFile.close();
outputFile.close();
}
cout << "所有测试用例生成完成！" << endl;
return 0;
}
题目要进团才能看见