SOJ1114（历史排名第130）

2017-11-17的排名

虽然用C可能会更快，但是这不是算法上的改良，所以这样改了没啥意义。
具体的题目就是这样的啦~

1114. Food Cubes

Constraints

Time Limit: 10 secs, Memory Limit: 32 MB

Description

The spacemen in the space shuttle are waiting for the next escape window to return to the mother land Earth, where they are expected to fall somewhere in the deep blue waters of the Persian Gulf. Bored of waiting with nothing to do, they decide to play a game with their unit size food cubes. In the zero gravity environment of their spaceship, anything can stay motionless where it is placed. One spaceman places several food cubes in space such that there may be holes between cubes. Others, given the coordinates of the food cubes, should find the number of holes. A hole is a continuous empty space surrounded by food cubes in all six directions. You are to write a program to read the coordinates of each food cube and compute the number of holes.

Input

The first line of the input contains a single integer t (1 <= t <= 20) which is the number of test cases in the input. Each test case starts with an integer M, the number of food cubes. Each line i (1 <= i <= M) of the M following lines contains integers xi, yi and zi, all between 1 and 100 inclusive, indicating the three coordinates of a food cube in the 3D space.

Output

For each test case, there is one line containing the number of holes.

Sample Input

2
26
1 1 1
1 2 1
1 3 1
2 1 1
2 2 1
2 3 1
3 1 1
3 2 1
3 3 1
1 1 2
1 2 2
1 3 2
2 1 2
2 3 2
3 1 2
3 2 2
3 3 2
1 1 3
1 2 3
1 3 3
2 1 3
2 2 3
2 3 3
3 1 3
3 2 3
3 3 3
7
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
Sample Output

1
0

下面的代码用了0.12secAC了，在这提供大家学习一下。（很大几率是给我以后的的师弟或者师妹刷SOJ的是遇到问题了来看的时候）

#include <iostream>
using namespace std;
#include <queue>
#include <cstring>
#include <algorithm>
#define INF 1<<30
#define MINF 1<<31
bool map[103][103][103]; // true 表示是障碍，否则就不是障碍 
bool visited[103][103][103]; // true表示访问过 
int ans;
struct Node{
    int x, y, z;
    Node(int a = 0, int b = 0, int c = 0):x(a), y(b), z(c){};
}; 
int op[][6] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int main(){
    int t, time, x, y, z, a, b, c,maxx,minx,maxy,miny,maxz,minz;
    bool wrong;
    cin >> t;
    while (t--) {
        cin >> time;
        memset(map, false, sizeof(map));
        memset(visited, false, sizeof(visited));
        ans = 0; 
        maxx=maxy=maxz=MINF;
        minx=miny=minz=INF;
        while(time --) {
            cin >> x>> y>> z;
            map[x][y][z] = true;//设置障碍
            maxx = max(x,maxx);
            maxy = max(y,maxy);
            maxz = max(z,maxz);
            minx = min(x,minx);
            miny = min(y,miny);
            minz = min(z,minz);
        }
        for (x = minx; x <= maxx; ++x)
        for (y = miny; y <= maxy; ++y)
        for (z = minz; z <= maxz; ++z) {
            if ( !map[x][y][z] && !visited[x][y][z]) {  
                queue<Node> q;
                q.push(Node(x,y,z));
                wrong = false;
                visited[x][y][z] = true;
                while (!q.empty()) {
                    Node now = q.front();
                    q.pop();
                    for (int i = 0; i < 6; ++i) {
                        a = now.x + op[i][0];
                        b = now.y + op[i][1];
                        c = now.z + op[i][2];
                        if (a < minx|| b < miny|| c < minz|| a > maxx|| b > maxy|| c > maxz) {
                            wrong = true;
                        } else if ( !map[a][b][c] && !visited[a][b][c]) {
                            q.push(Node(a,b,c));
                            visited[a][b][c] = true;
                        }
                    }
                }
                if (!wrong) {
                    ans ++;
                }
            }
        }
        cout << ans<< endl;
    }
}