# 题目

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).

## 代码

```#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;
} ```

0 条评论

• ### C. NEKO's Maze Game

time limit per test:1.5 seconds memory limit per test:256 megabytes inputstandar...

• ### POJ-2585-Window Pains

Window PainsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 2915 ...

• ### Ceph用户邮件列表Vol45-Issue3

https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=af5e5...

• ### 关于无意识匹配问题

作者：Zhihao Gavin Tang,Xiaowei Wu,Yuhao Zhang

• ### 【CodeForces 602C】H - Approximating a Constant Range（dijk）

In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional rai...

• ### 【短道速滑四】Halcon的texture_laws算子自我研究

Halcon里有个texture_laws 算子，最近实现了下，记录下相关细节。

• ### HDUOJ----2489 Minimal Ratio Tree

Minimal Ratio Tree Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768...

• ### Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2)(A.暴力，B.优先队列，C．dp乱搞)

A. Carrot Cakes time limit per test：1 second memory limit per test：256 megabytes...

• ### IOS5开发-控件位置适应屏幕旋转代码

- (void)willRotateToInterfaceOrientation:(UIInterfaceOrientation)toOrientation  ...