2014-05-31

UVa 1030 - Image Is Everything

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

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

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

Solution

題目描述：

現在有一些著色的立方體 1x1x1，每一個立方小塊會由一個顏色構成，然後這些立方塊會疊在一起，最大為 N N N 。機器人在周圍拍照，將六個影像傳回來，請問現在最多可能有多少立方塊。

題目解法：

這題最麻煩的是座標假想。

現在眼前有一個立方體，而前方是 Y 軸正向，右手是 X 軸正向，上方是 Z 軸正向。

而對於每一個面來說，機器人相當於在 X-Y 平面上走動。拍攝的時候，X 軸是往下方正向，Y 軸是往右方正向。

接著，先把空洞挖掉。再者，把所有可能進行標記，接著嘗試把那一面貼上去，對於不符合顏色的立方塊拔掉，直到六個面都屬於符合的狀態 (迭代更新)。

#include <stdio.h> 
#include <string.h>
char cube[16][16][16];
// front, left, back, right, top, bottom
void getXYZ(int N, int kind, int x, int y, int d, int &rx, int &ry, int &rz) {
    switch(kind) {
        case 0:
            rx = y, ry = d, rz = N - x - 1;
            break;
        case 1:
            rx = d, ry = N - y - 1, rz = N - x - 1;
            break;
        case 2:
            rx = N - y - 1, ry = N - d - 1, rz = N - x - 1;
            break;
        case 3:
            rx = N - d - 1, ry = y, rz = N - x - 1;
            break;
        case 4:
            rx = y, ry = N - x - 1, rz = N - d - 1;
            break;
        case 5:
            rx = y, ry = x, rz = d;
            break;
    }
}
int main() {
    char views[6][16][16];
    for(int N; scanf("%d", &N) == 1 && N; )  {
        int x, y, z;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < 6; j++)
                scanf("%s", &views[j][i]);
        }
        
        memset(cube, '?', sizeof(cube));
        
        for(int k = 0; k < 6; k++) {
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    if(views[k][i][j] != '.')
                        continue;
                    for(int d = 0; d < N; d++) {
                        getXYZ(N, k, i, j, d, x, y, z);
                        cube[x][y][z] = '.';
                    }
                }
            }
        }
        bool update = false;
        do {
            update = false;
            for(int k = 0; k < 6; k++) {
                for(int i = 0; i < N; i++) {
                    for(int j = 0; j < N; j++) {
                        if(views[k][i][j] == '.')
                            continue;
                        for(int d = 0; d < N; d++) {
                            getXYZ(N, k, i, j, d, x, y, z);
                            if(cube[x][y][z] == '.')
                                continue;
                            if(cube[x][y][z] == '?') {
                                cube[x][y][z] = views[k][i][j];
                                update = true;
                                break;
                            } else if(cube[x][y][z] == views[k][i][j]) {
                                break;	
                            } else {
                                cube[x][y][z] = '.';
                                update = true;
                            }
                        }
                    }
                }
            }
        } while(update == true);
        
        int ret = 0;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                for(int k = 0; k < N; k++)
                    ret += cube[i][j][k] != '.';
        printf("Maximum weight: %d gram(s)\n", ret);
    }
    return 0;
}
/*
front, left, back, right, top, bottom.
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
*/

Morris' Blog