POJ 3792 Area of Polycubes（思维）

题意：其实我也说不太清楚题意，就是给你很多方块，每放一块方块，都要和前一块有一个面相接，如果不相接，就输出NO，并输出是第几个方块不相接的。如果满足每一个都和前边相接，那就判断所有没有与其他方块相接的面的个数。

思路：每输入一个就判断前一个的上下左右前后中距离为1的有没有这个点，如果没有就记录下位置，用于输出NO，如果有的话，就记录下来，然后减去两个面，因为两个方块相接，有两个面要被减去，ans先初始化为6*m，相当于先初始化为所有的面。

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <set>

#include <algorithm>

using namespace std ;

//int dir[3][6] = {{-1,0,1,0,0,0},{0,-1,0,1,0,0},{0,0,0,0,-1,1}} ;

int dirx[] = {-,,,,,};

int diry[] = {,-,,,,};

int dirz[] = {,,,,-,};

struct node

{

    int x,y,z ;

}temp1,temp2;

bool operator <(node a,node b)

{

    if(a.x == b.x)

    {

        if(a.y == b.y)

        {

            return a.z < b.z ;

        }

        return a.y < b.y ;

    }

    return a.x < b.x ;

}

int main()

{

    set<node>sett ;

    int n ,m,cas = ;

    scanf("%d",&n)     ;

    while(n--)

    {

        scanf("%d",&m) ;

        int ans = m* ;

        int flag = - ;

        sett.clear() ;

        scanf("%d,%d,%d",&temp1.x,&temp1.y,&temp1.z) ;

        sett.insert(temp1) ;

        for(int i =  ; i <= m ; i++)

        {

            scanf("%d,%d,%d",&temp1.x,&temp1.y,&temp1.z) ;

            if(flag == - && sett.find(temp1) != sett.end())

                flag = i ;

            if(flag == -)

            {

                int cnt =  ;

                for(int j =  ; j <  ; j++)

                {

                    temp2.x = temp1.x+dirx[j] ;

                    temp2.y = temp1.y+diry[j] ;

                    temp2.z = temp1.z+dirz[j] ;

                    if(sett.find(temp2) != sett.end()) cnt++ ;

                }

                if(cnt) ans -= cnt* ;

                else flag = i ;

                sett.insert(temp1) ;

            }

        }

        if(flag != -) printf("%d NO %d\n",cas++,flag) ;

        else printf("%d %d\n",cas++,ans) ;

    }

    return  ;

}

巴特西

POJ 3792 Area of Polycubes（思维）

最新文章

热门文章