posts - 33,  comments - 33,  trackbacks - 0
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3682
题目大意:给你一个立方体,要求去掉若干个垂直于xy或xz或yz的柱子后,去掉的总立方块个数。
题解:发挥想象力,模拟。
1.判断两两相交
例子:
设柱子的值为(x,y,z),其中用0表示和该轴平行
柱子A:(x1,y1,0),表示过xy平面的x1,y1点,且垂直于xy平面
柱子B:(0,y2,z2),表示过yz平面的y2,z2点,且垂直于yz平面
如果柱子A和柱子B相交,那么必有:y1 == y2
如A*B中有两个分量为0,且非0部分两者相等,则相交,交点为两者求并(x1,y1==y2,z2)

2.逐个插入
那么,根据给出的柱子数,初始移除块数为n*m,然后按照数据顺序逐个插入
并且判断有没有重复,注意每次插入时,判重Hash都是初始的,就是说,以前
出现过交点的,并不会影响下一次的交点判断

代码:
#include <stdio.h>
#include 
<set>
#include 
<vector>
#include 
<time.h>
#include 
<stdlib.h>
using namespace std;

const int N = 1005;
struct Point
{
    
int x;
    
int y;
    
int z;
    Point(
int _x = 0,int _y = 0,int _z = 0):x(_x),y(_y),z(_z){}
}
;

vector
<Point> vecX[N];
vector
<Point> vecY[N];
vector
<Point> vecZ[N];
set<long long> Set;
int n,m;
int cnts[128];

long long Hash(int x,int y,int z)
{
    
long long c = (long long)x*10000*10000;
    c
*= 10;
    
return c+ (long long)y * 10000 + (long long)z;
}


bool IsCross(Point &_p1,Point& _p2,set<long long>& _Set)
{
    
int cx = _p1.x * _p2.x;
    
int cy = _p1.y * _p2.y;
    
int cz = _p1.z * _p2.z;
    
if(((cx == 0)&&(cy == 0))||((cx == 0)&&(cz == 0))||((cy == 0)&&(cz == 0)))
    
{
        Point p3;
        
if((cx != 0)&&(_p2.x == _p1.x))
        
{
            p3.x 
= _p1.x;
            p3.y 
= _p1.y | _p2.y;
            p3.z 
= _p1.z | _p2.z;
        }

        
else if((cy != 0)&&(_p2.y == _p1.y))
        
{
            p3.x 
= _p1.x | _p2.x;
            p3.y 
= _p1.y;
            p3.z 
= _p1.z | _p2.z;
        }

        
else if((cz != 0)&&(_p2.z == _p1.z))
        
{
            p3.x 
= _p1.x | _p2.x;
            p3.y 
= _p1.y | _p2.y;
            p3.z 
= _p1.z;
        }

        
long long hashCode = Hash(p3.x,p3.y,p3.z);
        
if(_Set.find(hashCode) == _Set.end())
        
{
            _Set.insert(hashCode);
            
return true;
        }

        
else
        
{
            
return false;
        }

    }

    
return false;
}


int Insert()
{
    Point p1(cnts[
'X'],cnts['Y'],cnts['Z']);
    
long long hashCode = Hash(p1.x,p1.y,p1.z);
    
//判断出现相同的柱子
    if(Set.find(hashCode) != Set.end())
        
return n;
    
else
        Set.insert(hashCode);
    
//对于每一次插入,Hash都是初始的
    set<long long> tmpSet;
    
int crossCnt = 0;
    
if(p1.x != 0)
    
{
        
for(int i = 0; i < vecX[p1.x].size(); ++i)
        
{
            
if(IsCross(p1,vecX[p1.x][i],tmpSet))
                crossCnt
++;
        }

        vecX[p1.x].push_back(p1);
    }

    
if(p1.y != 0)
    
{
        
for(int i = 0; i < vecY[p1.y].size(); ++i)
        
{
            
if(IsCross(p1,vecY[p1.y][i],tmpSet))
                crossCnt
++;
        }

        vecY[p1.y].push_back(p1);
    }

    
if(p1.z != 0)
    
{
        
for(int i = 0; i < vecZ[p1.z].size(); ++i)
        
{
            
if(IsCross(p1,vecZ[p1.z][i],tmpSet))
                crossCnt
++;
        }

        vecZ[p1.z].push_back(p1);
    }

    
return crossCnt;
}


void Test()
{
    scanf(
"%d %d\n",&n,&m);
    
for(int i = 0; i < N; ++i)
    
{
        vecX[i].clear();
        vecY[i].clear();
        vecZ[i].clear();
    }

    Set.clear();
    
char ch1,ch2;
    
int d1,d2;
    
int all = n*m;
    
for(int i = 0; i < m; ++i)
    
{
        cnts[
'X'= cnts['Y'= cnts['Z'= 0;
        
//getchar();
        scanf("%c=%d,%c=%d\n",&ch1,&d1,&ch2,&d2);
        cnts[ch1] 
= d1;
        cnts[ch2] 
= d2;
        all 
-= Insert();
    }

    printf(
"%d\n",all);
}



int main()
{
    
int testcase = 0;
    scanf(
"%d",&testcase);
    
for(int i = 0; i < testcase; ++i)
        Test();
    
return 0;
}
posted on 2010-11-10 17:10 bennycen 阅读(437) 评论(1)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理