1054:Cube

总时间限制:

 

1000ms

内存限制:

131072kB

 
描述

Delayyy君很喜欢玩某个由Picks编写的方块游戏,游戏在一个由单位格组成的棋盘上进行。

游戏的主角是一个6个面互不相同的小方块,每次可以向上下左右中的某个方向翻滚一格。

PKU Online Judge 1054:Cube (设置根节点)-LMLPHP
棋盘上有 N 个关键格子,对应于游戏中的村庄,在坐标系中,每个村庄有一个坐标位置 (x,y) (任意两个村庄位置不相等)。

先前的方块村民已经修好了 N-1 条道路(高架桥、地下隧道等,即不能从一条道路走上另一条道路)使这 N 个村庄连通,并且由于方块民族的习俗,每条道路都平行于坐标轴。

主角小方块打算选两个村庄 S 、 T ,沿最短路进行一次 S 到 T 的旅行。

但由于方块民族的特殊属性,小方块一次旅行终止时必须和开始时的状态(即六个面的朝向)完全一致。

Delayyy君想知道,从每个村庄出发,主角小方块能选出多少个可行的旅行终点。

数据范围

PKU Online Judge 1054:Cube (设置根节点)-LMLPHP

输入
一个测试点中有多组数据(不超过10组)。对于每组数据:

第一行一个整数:N。

接下来 N 行中的第 i 行中有两个整数:x[i], y[i],表示第 i 个关键格子(即村庄)的位置。

再接着 N-1 行,每行两个数:u, v,表示第 u 个关键格子和第 v 个关键格子之间有边。保证 x[u]=x[v] 或 y[u]=y[v]。

输出
对于每组数据:

输出共 N 行。

第 i 行表示从第 i 个关键格子开始滚动符合要求的方案数。

样例输入
1
1 1
3
1 1
1 2
5 1
1 2
1 3
样例输出
0
1
0
1
提示

对于第二个样例,仅有在1,3号关键格子中滚动时不会改变状态。

思路:

如果求任意两点间是否能到达的话,那枚举两个点就是O(n*n)了,要超时了。所以想到设置一个根节点,一遍dfs就能求出根节点到其他点的状态,那么如果到达两个点的状态相同的话,就知道这两个点能相互到达了,因为p1->p2 = p1->根->p2。状态的话将cube编号,存上、前、右三个面的值就够了(两个也可以,但是滚动时没有三个方便)。

ps:一个点到一个点状态是否变化不能简单的用x之差与y之差%4==0来简单判断.

顺便说一下那个其实不需要将状态编号的,我的代码多余了。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 100005
#define MAXN 20005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 0.000001
typedef long long ll;
using namespace std; int n,m,ans;
int px[maxn],py[maxn];
vector<int>edge[maxn];
bool vis[maxn];
int mp[7][7][7],num[50]; // mp-状态对应的编号 num-每个状态的个数
int s[maxn]; //s-每个点对应的状态
int obj[7]={0,6,5,4,3,2,1}; // 每个点的对立面 void dfs(int u,int x,int y,int z)
{
int i,j,t,tx,ty,tz,v,w;
s[u]=mp[x][y][z];
num[s[u]]++;
for(i=0;i<edge[u].size();i++)
{
v=edge[u][i];
if(!vis[v])
{
vis[v]=1;
if(px[v]==px[u])
{
if(py[v]>py[u]) // 上
{
w=py[v]-py[u];
w=w%4;
tx=x,ty=y;
for(j=1;j<=w;j++)
{
t=tx;
tx=ty;
ty=obj[t];
}
dfs(v,tx,ty,z);
}
else // 下
{
w=py[u]-py[v];
w=w%4;
tx=x,ty=y;
for(j=1;j<=w;j++)
{
t=tx;
tx=obj[ty];
ty=t;
}
dfs(v,tx,ty,z);
}
}
else
{
if(px[u]>px[v]) // 左
{
w=px[u]-px[v];
w=w%4;
tx=x,ty=y,tz=z;
for(j=1;j<=w;j++)
{
t=tx;
tx=tz;
tz=obj[t];
}
dfs(v,tx,ty,tz);
}
else // 右
{
w=px[v]-px[u];
w=w%4;
tx=x,ty=y,tz=z;
for(j=1;j<=w;j++)
{
t=tx;
tx=obj[tz];
tz=t;
}
dfs(v,tx,ty,tz);
}
}
}
}
}
int main()
{
int i,j,u,v;
memset(mp,0,sizeof(mp));
mp[1][2][4]=1,mp[1][3][2]=2,mp[1][4][5]=3,mp[1][5][3]=4; // 将状态编号
mp[2][1][3]=5,mp[2][3][6]=6,mp[2][6][4]=7,mp[2][4][1]=8;
mp[3][1][5]=9,mp[3][5][6]=10,mp[3][6][2]=11,mp[3][2][1]=12;
mp[4][2][6]=13,mp[4][6][5]=14,mp[4][5][1]=15,mp[4][1][2]=16;
mp[5][1][4]=17,mp[5][4][6]=18,mp[5][6][3]=19,mp[5][3][1]=20;
mp[6][2][3]=21,mp[6][3][5]=22,mp[6][5][4]=23,mp[6][4][2]=24;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
{
scanf("%d%d",&px[i],&py[i]);
edge[i].clear();
}
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
memset(num,0,sizeof(num));
memset(vis,0,sizeof(vis));
vis[1]=1;
dfs(1,1,2,4);
for(i=1;i<=n;i++)
{
printf("%d\n",num[s[i]]-1);
}
}
return 0;
}
04-26 11:56