PKU Online Judge 1054:Cube （设置根节点）

1054:Cube

总时间限制:

1000ms

内存限制:

131072kB

描述

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

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

棋盘上有 N 个关键格子，对应于游戏中的村庄，在坐标系中，每个村庄有一个坐标位置 (x,y) （任意两个村庄位置不相等）。

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

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

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

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

数据范围

输入

一个测试点中有多组数据（不超过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,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;

}

巴特西

PKU Online Judge 1054:Cube （设置根节点）

1054:Cube

最新文章

热门文章