Uva 1030.Image Is Everything

812

题目


Your new company is building a robot that can hold small lightweight objects.
The robot will have the intelligence to determine if an object is light enough to hold.
It does this by taking pictures of the object from the 6 cardinal directions, and then inferring an upper limit on the object’s weight based on those images.
You must write a program to do that for the robot.
You can assume that each object is formed from an N × N × N lattice of cubes, some of which may be missing.
Each 1 × 1 × 1 cube weighs 1 gram, and each cube is painted a single solid color.
The object is not necessarily connected.



Input  


The input for this problem consists of several test cases representing different objects.
Every case begins with a line containing N, which is the size of the object (1 ≤ N ≤ 10).
The next N lines are the different N × N views of the object, in the order front, left, back, right, top, bottom.
Each view will be separated by a single space from the view that follows it.
The bottom edge of the top view corresponds to the top edge of the front view.
Similarly, the top edge of the bottom view corresponds to the bottom edge of the front view.
In each view, colors are represented by single, unique capital letters, while a period (.) indicates that the object can be seen through at that location.

Input for the last test case is followed by a line consisting of the number ‘0’.


Output  


For each test case, print a line containing the maximum possible weight of the object, using the format
shown below.


Sample Input  


3
.R. YYR .Y. RYY .Y. .R.
GRB YGR BYG RBY GYB GRB
.R. YRR .Y. RRY .R. .Y.
2
ZZ ZZ ZZ ZZ ZZ ZZ
ZZ ZZ ZZ ZZ ZZ ZZ
0


Sample Output  


Maximum weight: 11 gram(s)
Maximum weight: 8 gram(s)



题解


一道非常不水的水题
没有用到任何算法,但是实现起来又到处都考验细节


首先是理解输入
n 列划分在一起,每部分的矩形分别是前视图,左视图,后视图,右视图,顶视图,底视图

要求出最多的方块数,因此任务就是找到一定不合理的方块删掉,然后计算出剩下的方块还有多少

不合理的方块有以下可能
  • 能够看透的方块
    本身不存在,必然不合理
  • 不同视图有矛盾的方块
    一个方块的颜色是确定的,不管从哪个方向看一定是一样的

因此工作就是不同的从各个方向看这个立方体,判断每个方块是不是合理

使用 get() 函数获得从某个视图看 (a,b) 格第一个可能合法的方块(前面的方块已确定不存在)

使用 lp() 函数分担循环的工作
根据参数的不同进行顺序和逆序循环及需要循环的维度


如图是各个视图与方块的对应关系
根据对应关系确定某个视图应该是顺序查找还是逆序查找, (a,b) 对应的分别是哪个维度

一直找到所有方块全部都合法为止,统计还存在的方块

代码


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;
const int maxn = 16;

//前 左 后 右 顶 底
char view[6][maxn][maxn];
char cube[maxn][maxn][maxn];
int n;

bool lp(bool sx,int &x,int &y,int &z,int a = -1,int b = -1,int c = -1) {
    int *i = &a;
    if(a == -1)
        i = &a;
    if(b == -1)
        i = &b;
    if(c == -1)
        i = &c;
    if(sx) {
        for((*i) = 0;(*i) < n;(*i)++) {
            if(cube[a][b][c] != -1) {
                x = a;
                y = b;
                z = c;
                return true;
            }
        }
    } else {
        for((*i) = n - 1;(*i) >= 0;(*i)--) {
            if(cube[a][b][c] != -1) {
                x = a;
                y = b;
                z = c;
                return true;
            }
        }
    }
    return false;
}

bool Get(int v,int a,int b,int &x,int &y,int &z) {
    if(v == 0)//从前往后
        return lp(true,x,y,z,-1,a,b);
    else if(v == 1)//从左往右
        return lp(true,x,y,z,n - 1 - b,a,-1);
    else if(v == 2)//从后往前
        return lp(false,x,y,z,-1,a,n - 1 - b);
    else if(v == 3)//从右往左
        return lp(false,x,y,z,b,a,-1);
    else if(v == 4)//从上到下
        return lp(true,x,y,z,n - 1 - a,-1,b);
    else//从下到上
        return lp(false,x,y,z,a,-1,b);
}

int Do() {
    cin >> n;
    if(n == 0)
        return false;

    for(int i = 0;i < n;i++)
        for(int j = 0;j < 6;j++)
            for(int k = 0;k < n;k++)
                cin >> view[j][i][k];

    memset(cube,0,sizeof(cube));

    bool flag = true;

    while(flag) {
        flag = false;
        for(int i = 0;i < 6;i++)
            for(int j = 0;j < n;j++)
                for(int k = 0;k < n;k++) {
                    int x,y,z;
                    if(Get(i,j,k,x,y,z)) {
                        if(view[i][j][k] == '.') {
                            //可以看透
                            cube[x][y][z] = -1;
                            flag = true;
                        } else {
                            if(cube[x][y][z] == 0) {
                                //未涂色的方块
                                cube[x][y][z] = view[i][j][k];
                                flag = true;
                            } else if(cube[x][y][z] != view[i][j][k]) {
                                //涂色产生矛盾
                                cube[x][y][z] = -1;
                                flag = true;
                            }
                        }
                    }
                }
    }

    int ans = 0;
    for(int i = 0;i < n;i++)
        for(int j = 0;j < n;j++)
            for(int k = 0;k < n;k++)
                if(cube[i][j][k] != -1)
                    ans++;

    cout << "Maximum weight: " << ans << " gram(s)" << endl;

    return true;
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    while(Do());

    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论