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

By | 10月15日
Advertisement

1054:Cube

总时间限制:

1000ms 内存限制: 131072kB

描述

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

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

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

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

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

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

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

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

数据范围

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

输入
一个测试点中有多组数据(不超过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;
}

Similar Posts:

  • ztree 默认设置选中第一个子节点,根节点禁止选中(只有一个根结点时);选中想选中的子节点

    $(document).ready(function(){    $.fn.zTree.init($("#architectureTreeId"), setting,eval(${(architectureTree)!}));   var zTree = $.fn.zTree.getZTreeObj("architectureTreeId");   var nodes = zTree.getNodes();   zTree.checkNode(nodes[0], f

  • [置顶] 树寻找根节点

    // // main.cpp // 寻找根节点 // // Created by liujan on 1/13/15. // Copyright (c) 2015 liujan. All rights reserved. // #include <iostream> #include "memory.h" using namespace std; /* *每个节点的id在输入父节点时被输入一次,输入本身时一次,两个子节点时又两次,所以其输入次数肯定为偶数 *根节点只会被输入

  • 若一颗二叉树的前序遍历为a,e,b,d,c,后序遍历为b,c,d,e,a,则根节点的孩子节点()

    若一颗二叉树的前序遍历为a,e,b,d,c,后序遍历为b,c,d,e,a,则根节点的孩子节点() --cut-- tiyee在2015-06-20 05:06:50回答到: StinsonZhao在2015-06-20 09:30:49回答到: 树是这样的,a是根,e可以是左也可以是右子节点,e的左节点是b,右节点是d,d的左节点是c

  • hdu 2545(并查集求节点到根节点的距离)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2545 思路:dist[u]表示节点u到根节点的距离,然后在查找的时候更新即可,最后判断dist[u],dist[v]的大小即可. 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<vector> 6 using na

  • POJ2492A Bug&#39;s Life【并查集+根节点偏移】

    大意: 告诉你一些关系 a b 代表 a 和 b 是异性 问这些关系中有没有错误的语句 分析: 有并查集维护其是否在同一个集合之中 在开一个num数组来维护对于根节点的偏移量 在find的时候只需要递归到根节点返回的过程中把num数组进行维护就可以了 在进行合并的时候我们需要考虑到把一个点的根节点并到另一个的根节点上 所以要根据u和v的偏移关系推广到u和v的根节点的关系之上 代码: 1 #include <iostream> 2 #include <cstdio> 3 #inclu

  • 杭电1213 How Many Tables(并查集找根节点)

    How Many Tables Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 18215 Accepted Submission(s): 8975 Problem Description Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner tim

  • DOM节点信息、DOM属性、三大节点、替换节点、查找设置属性节点、创建删除插入节点、innerHTML属性、显示弹出窗口

    DOM节点信息.DOM属性.三大节点.替换节点.查找设置属性节点.创建删除插入节点.innerHTML属性.显示弹出窗口 DOM节点信息 每个节点都拥有包含着关于节点某些信息的属性.这些属性是: nodeName(节点名称) nodeValue(节点值) nodeType(节点类型) DOM属性---nodeName nodeName 属性含有某个节点的名称. var name = node.nodeName; 元素节点的 nodeName 是标签名称 属性节点的 nodeName 是属性名称

  • 求助,我想要做一个能够用树型结构显示会员级别的网页,1个根节点,有3个字节点。

    我想要做一个能够用树型结构显示会员级别的网页,1个根节点,有3个字节点.不知道该怎么做.

  • 关于Dwz的tree全选子节点后,根节点没有选中的解决方案

    今天在写demo的时候,突然发觉一个问题,问题描述如下: 在手动一个一个选中子节点的情况下,状态为全选,根节点的复选框是选中的,但是出现一个问题,循环遍历的时候,只 能找到选中的子节点,而选中的根节点复选框状态还是false,我仔细看了一下源码,做了如下修改: 在dwz.tree.js文件中: _checkParent: function () { if ($(this).parent().hasClass("tree")) return; var parent = $(this).p

  • Qt QTreeView根节点下不显示数据(Thinkvd开发日志)

    现象描述:当在Clip后返回主界面时,Clip后的记录B会从当前的记录A COPY一份,并在记录B下生成子记录B1.B2.关系如下: A B "--B1 |--B2 此时记录B的子节点与B一块显示不出来,若B1,B2直接为记录A的子节点是没有问题,其记录B新增加的方式与已经存在增加addProfile类似.测试若把B当成A的子记录,如下关系: A |--B |--B1 |--B2 这时显示没有问题. 简化代码: //itemData 相当于B //item 相当于A, A,B为兄弟节点 item

Tags: