題目鏈接：
http://acm.hdu.edu.cn/showproblem.php?pid=3682題目大意：給你一個(gè)立方體，要求去掉若干個(gè)垂直于xy或xz或yz的柱子后，去掉的總立方塊個(gè)數(shù)。
題解：發(fā)揮想象力，模擬。
1.判斷兩兩相交
例子：
設(shè)柱子的值為(x,y,z)，其中用0表示和該軸平行
柱子A：(x1,y1,0)，表示過xy平面的x1,y1點(diǎn)，且垂直于xy平面
柱子B：(0,y2,z2)，表示過yz平面的y2,z2點(diǎn)，且垂直于yz平面
如果柱子A和柱子B相交，那么必有：y1 == y2
如A*B中有兩個(gè)分量為0，且非0部分兩者相等，則相交，交點(diǎn)為兩者求并(x1,y1==y2,z2)
2.逐個(gè)插入
那么，根據(jù)給出的柱子數(shù)，初始移除塊數(shù)為n*m，然后按照數(shù)據(jù)順序逐個(gè)插入
并且判斷有沒有重復(fù)，注意每次插入時(shí)，判重Hash都是初始的，就是說(shuō)，以前
出現(xiàn)過交點(diǎn)的，并不會(huì)影響下一次的交點(diǎn)判斷
代碼：
#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);
//判斷出現(xiàn)相同的柱子
if(Set.find(hashCode) != Set.end())
return n;
else
Set.insert(hashCode);
//對(duì)于每一次插入，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 閱讀(497)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
算法題解