2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

题目链接：G. Projection

题目

Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged to recreate the TensorFlow logo from two projections.

Consider that you have a 3D volume, n×m×h, and two projections (two matrices with dimensions n×m and n×h with elements 0 and 1). You are asked to compute a possible sets of cubes that must be placed inside the 3D volume such that the 3D object created with the cubes throws the shadows specified by the projection-matrices, when the light comes from left and front. If it is not possible, just print −1. If it is possible you must find exactly two sets, one with the maximum amount of cubes and one with the minimum amount. You can assume there is no gravitation (the cubes are located inside the 3D volume exactly where they are placed, without requiring any support). We assume that 1 represents shadow and 0 represents light.

If there are multiple such solutions, you must output the minimum lexicographic one. One solution A is lexicographically smaller than another solution b if the first number that differs between the two solutions is smaller in a than in b.

For example, solution [(0,0,0),(1,1,1)] is smaller than [(1,1,1),(0,0,0)].

Input The first line contains three integers separated by a single space n, m, h (1≤n,m,h≤100) — the volume dimensions.

Each of the next n lines contains m characters, each being either 1 or 0 representing either a shadow area (1) or a light area (0), describing the projection from the light in the front.

Each of the next n lines contains h characters, with the same format as above, describing the projection from the light on the left.

Output The output should contain on the first line one number, either −1 if there is no solution or kmax representing the maximum number of cubes we can assign in the volume that will generate the two projections given in the input.

The next kmax lines should contain triplets of numbers x, y, z (0≤x<n, 0≤y<m, 0≤z<h) representing the cubes chosen in the lexicographically smallest solution with maximum number of cubes.

Then, only if there is a solution, one more line follows containing kmin, the minimum number of cubes we can assign in the volume that will generate the two projections given in the input.

After that, the next kmin lines should contain triplets of numbers x, y, z (0≤x<n, 0≤y<m, 0≤z<h) representing the cubes in the lexicographically smallest solution with minimum number of cubes.

input

5 3 3
111
010
010
010
010
111
100
110
100
100

output

14
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 1 0
2 1 0
2 1 1
3 1 0
4 1 0
8
0 0 0
0 1 1
0 2 2
1 1 0
2 1 0
2 1 1
3 1 0
4 1 0

input

2 2 2
00
00
11
11

output -1 input

2 3 2
101
011
10
11

output

6
0 0 0
0 2 0
1 1 0
1 1 1
1 2 0
1 2 1
4
0 0 0
0 2 0
1 1 0
1 2 1

Note A cube at coordinates (x,y,z) will generate a shadow at line x and column y in the n×m projection and line x and column z in the n×h projection (indexed from 0).

题目大意

给你一个立方体的侧面投影和正面的投影，1表示是阴影部分，0表示没有；让你判断它是否可以组成一个立方体，如果能那就先输出需要花费最多的小方块的个数，接着输出小方块的位置，再输出需要花费最少的小方块的个数，和他们的位置，如果不能的话就输出-1，本题忽略万有引力（也就是小方块可以腾空放置，还好忽略了要不然真的是不会搞了），输出的是也是有规定的，就是输出的时候输出字典序最小的一组方案（真是要求多）

解题思路

我们首先判断是否成立，如何判断呢？我们可以将左侧投影有压缩到 n 轴上，正面的也压缩的n轴上，然后比较在 n 轴的同一个位置如果正面的投影或者侧面的投影一个为零另一个却不为零的时候就不成立！直接输出 -1； 最大值也好判断，只要侧面投影的一个位置是阴影就去遍历正面的投影的 n 轴的m个位置，只有是影音就将这个位置存起来；计算过程中找个计数器遇到成立的情况就 +1； 最小值 最小值有点麻烦，当我们去求最小值的时候，先要知道侧面投影和正面投影的这一层有几个阴影，因为需要字典序最小，那么我们就要尽可能的让侧面的第一个位置对应的立体空间出放，如果侧面投影比正面的的数量多，我们就想让侧面的位置向后移动去放小方块，如果侧面的比正面的少，那就让侧面的先不动，让正面的向后移动，当然相等的时候就一起向后移动就行了； 比如说第 1 层吧；侧面投影是011010，正面投影是101； 那么我在第一层摆放的的方案应该是（1,1,0）,（1,2,1）,（1,4,2）这个就是先移动侧面的 说的不是很清，直接看代码吧！这个题挺傻逼的，自己模拟几遍应该就没问题了

代码

#include<bits/stdc++.h>
using namespace std;
int hang[109],lie[109];

int zuo[109][109];
int zheng[109][109];

int n,m,h;

struct node{
    int x,y,z;
}Max[1000009],Min[1000009];//分别存最大值和最小值时的 注意 立体坐标 n*m*h最大是1e6； 

int main()
{
    scanf("%d%d%d",&n,&m,&h);
    int f;
    for(int i=0;i<n;i++)
    {
        f=0;
        for(int j=0;j<m;j++)
        {
            scanf("%1d",&zuo[i][j]);
            f=f+zuo[i][j];
        }
        hang[i]=f;//每次记录侧面投影有几个阴影小块 
    }

    for(int i=0;i<n;i++)
    {
        f=0;
        for(int j=0;j<h;j++)
        {
            scanf("%1d",&zheng[i][j]);//每次记录正面投影有几个阴影小块
            f+=zheng[i][j];
        }
        lie[i]=f;
    }
    for(int i=0;i<n;i++){//判断是否可行 
        if(((hang[i]+lie[i])==max(hang[i],lie[i]))&&(hang[i]+lie[i])) {
            puts("-1");
            return 0;
        }
    }
//*************数量最多的情况 ***************

    int sum=0;
    for(int i=0;i<n;i++)//从第一层开始遍历 
    {
        for(int j=0;j<m;j++)//侧面 第 i层的第一个位置开始 
        {
            if(zuo[i][j])//如果这个位置是 1 那么就让第 i 层 的的正面的有可能是阴影的地方都是阴影 
            {
                for(int k=0;k<h;k++)
                {
                    if(zheng[i][k])//如果这个正面投影的第 i 层第 k 课位置是阴影 
                    {
                        Max[sum].x=i;// 那么在立体坐标中 （i，j， k） 这个位置就是阴影 
                        Max[sum].y=j;
                        Max[sum++].z=k;
                    }
                }
            }
        }
    }

//********************数量最少的情况*********************** 
    int ans=0;
    queue<int>qf,ql;//这个地方用vector也是可以的 
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++) if(zuo[i][j]) qf.push(j); //先将侧面投影中出现阴影的坐标放入侧面队列中 
        for(int j=0;j<h;j++) if(zheng[i][j]) ql.push(j);//正面投影也如此投影 
        while(qf.size()>ql.size()) {//如果侧面的数量比正面的多，就让侧面向后的位置在 m 列的阴影处放 
            Min[ans].x=i;
            Min[ans].y=qf.front();
            Min[ans++].z=ql.front();
            qf.pop();//弹出第一个元素 
        }
        while(qf.size()<ql.size())// 如果正面的比侧面的多，那么就让侧面的先跑 
        {
            Min[ans].x=i;
            Min[ans].y=qf.front();
            Min[ans++].z=ql.front();
            ql.pop();
        }
        while(!qf.empty())//一样的时候就一起跑 
        {
            Min[ans].x=i;
            Min[ans].y=qf.front();
            Min[ans++].z=ql.front();
            ql.pop();
            qf.pop();
        }
    }
// 完结散花，输出数量和坐标 
    printf("%d\n",sum);
    for(int i=0;i<sum;i++) printf("%d %d %d\n",Max[i].x,Max[i].y,Max[i].z);
    printf("%d\n",ans);
    for(int i=0;i<ans;i++) printf("%d %d %d\n",Min[i].x,Min[i].y,Min[i].z);
    return 0;
}