P5802 [SEERC2019]Projection题解
一道模拟题。
题目说了让求两种情况，我这里也就分两种情况来说明。
在这之前先说明一下无解的情况。
无解的情况有且只有一种，就是对于某一层，一个视图里面有阴影而另一个视图里面没有。
块数最多
容易想到能填上的位置的都填上这一想法。
那么我们对于某一层正视图上的每一个阴影方块，找到同一层右视图中每一个阴影方块，在两者交汇的位置上放上一个方块，就可以把所有能填上的位置都填上方块了。
比如下图：
块数最少
当某一层正视图与右视图阴影数量一样多的时候，可以明显想到一一对应这一解法。
而当数量不同的时候，我采用的策略是让多的一侧多出来的那一部分与少的一侧的第一个阴影匹配。
比如下面两个图：
两图分别说明了正视图与右视图多出来的时候的解决方法。
实现
这里我使用 vector 存储代表方块的结构体，全部放进去之后再一遍 sort()，最后遍历输出答案即可。
为了方便遍历，我同样使用了 vector 来存储每一层两个视图的阴影状态，只不过这里是倒序存储的。
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 110;
int n, m, h;
vector<int>frn[N], rgh[N];//front & right
struct Block
{
int x, y, z;
Block(int _x, int _y, int _z)
{
x = _x, y = _y, z = _z;
}
bool operator < (const Block &a) const
{
return (x == a.x) ? (y == a.y) ? (z < a.z) : (y < a.y) : (x < a.x);
}
};
void solveMax()
{
vector<Block>ans;
for(int i = 0; i < n; i++)
for(int j : frn[i])
for(int k : rgh[i])
ans.emplace_back(i, j, k);
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for(auto i : ans)
printf("%d %d %d\n", i.x, i.y, i.z);
}
void solveMin()
{
vector<Block>ans;
for(int i = 0; i < n; i++)
{
if(frn[i].size() < rgh[i].size())
{
for(int j = 0; j < rgh[i].size(); j++)
ans.emplace_back(i, frn[i][min((int)frn[i].size() - 1, j)], rgh[i][j]);
}
else if(frn[i].size() > rgh[i].size())
{
for(int j = 0; j < frn[i].size(); j++)
ans.emplace_back(i, frn[i][j], rgh[i][min((int)rgh[i].size() - 1, j)]);
}
else
{
for(int j = 0; j < frn[i].size(); j++)
ans.emplace_back(i, frn[i][j], rgh[i][j]);
}
}
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for(auto i : ans)
printf("%d %d %d\n", i.x, i.y, i.z);
}
int main()
{
scanf("%d%d%d", &n, &m, &h);
for(int i = 0; i < n; i++)
{
string s;
cin >> s;
for(int j = m; ~j; j--)
if(s[j] == '1')frn[i].push_back(j);
}
for(int i = 0; i < n; i++)
{
string s;
cin >> s;
for(int j = h; ~j; j--)
if(s[j] == '1')rgh[i].push_back(j);
}
for(int i = 0; i < n; i++)
{
if(frn[i].empty() ^ rgh[i].empty())
{
puts("-1");
return 0;
}
}
solveMax();
solveMin();
return 0;
}