TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6392
  • 题目
  • P6392[文科综合]地理
    限制 : 时间限制 : 10000 MS   空间限制 : 524288 KB
    评测说明 : 1s,512MB
    问题描述

    nodgd身处的星球很神奇,是个$n\times n\times n$的正方体,nodgd可以在星球的表面走动。星球表面每个面上有$n\times n$个正方形区域,其中一些地方是平地,另外一些地方是障碍物。nodgd只能在平地上行走,每次可以走进与当前这块平地有公共边的相邻平地(可以跨过正方体的棱到达另一个面),不能进入或者越过障碍物。nodgd每移动一格需要耗费$1$秒。

    另外,星球上还有$m$个虫洞,每个虫洞连接了星球上的两块平地,可以双向通行。nodgd可以通过虫洞来移动,每经经过一次虫洞也需要耗费$1$秒。

    现在nodgd想知道,从星球上的一块平地走到另一块平地,最少要花多少时间,如果不能到达则输出$-1$。为了体现nodgd的毒瘤性,nodgd会进行$q$次提问。

    输入格式

    第一行一个整数$n$,表示星球的大小。

    接下来是一个$n\times n$的只含01的字符矩阵,表示星球的上表面;接下是一个$n\times 4n$的01字符矩阵,划分为$4$个$n\times n$的字符矩阵后分别表示左表面、前表面、右表面、后表面;接下来是一个$n\times n$的01字符矩阵,表示星球的下表面。其中0表示障碍,1表示平地。左表面矩阵的第一行与上表面矩阵的最后一行对应位置相邻,左表面矩阵的最后一行与下表面矩阵的第一行相邻。

    接下来一行一个整数$m$,表示虫洞的数量。

    接下来$m$行,每行以$\texttt{f1 x1 y1 f2 x2 y2}$的格式描述一个虫洞连接的两个点。其中$\texttt{f1,f2}$都是六个大写字母L,R,U,D,F,B之一,分别表示左表面、右表面、上表面、下表面、前表面、后表面;$x1,y1,x2,y2$都是正数,表示虫洞连接的两块平地分别在面内的第几行第几列,行和列以01矩阵输入的行和列为准。保证虫洞连接的是平地,不会连接障碍。

    接下来一行一个整数$q$,表示询问的数量。

    接下来$q$行,每行以$\texttt{f1 x1 y1 f2 x2 y2}$的格式描述一次提问的起点和终点。数据的含义与虫洞的相同,保证起点和终点都是平地。

    输出格式

    每次提问输出一行一个整数,表示这次询问的答案。

    样例输入 1

    3
    010
    111
    010
    010010000000
    010111111010
    010010000000
    110
    100
    111
    1
    B 2 2 D 3 3
    4
    U 2 2 U 2 2
    L 1 2 U 1 2
    F 2 1 D 1 1
    R 2 3 B 2 2

    样例输出 1

    0
    3
    10
    18

    样例输入 2

    4
    1111
    1111
    1111
    1111
    1111111111111111
    1111111111111111
    1111111111111111
    1111111111111111
    1111
    1111
    1111
    1111
    5
    D 4 2 U 1 3
    R 3 3 B 2 1
    D 3 1 F 3 3
    L 1 1 F 2 4
    L 4 1 B 4 1
    20
    B 1 2 F 3 3
    R 4 2 F 2 1
    L 2 2 U 2 2
    R 4 1 U 1 4
    B 2 4 R 4 2
    F 4 4 B 2 1
    R 4 3 U 4 1
    B 2 1 B 1 4
    B 4 3 L 1 1
    B 2 3 D 2 1
    U 3 4 R 1 4
    B 4 1 B 4 2
    F 4 4 L 2 2
    D 1 1 L 2 3
    L 3 1 B 1 3
    L 1 3 U 2 1
    B 4 2 F 4 2
    D 3 2 U 3 1
    F 2 3 B 3 3
    R 1 1 F 2 3

    样例输出 2

    5
    7
    4
    4
    6
    5
    7
    4
    5
    3
    6
    1
    5
    5
    4
    5
    4
    6
    5
    3

    提示

    数据规模与约定

    测试点1:\(n=1,\quad m=1,\quad q=50\)

    测试点2,3:没有障碍物;

    测试点4,5:\(m=0,\quad q\leq 1000\)

    测试点6:\(q=1\)

    测试点7,8:\(q\leq 1000\)

    测试点1~10:$1\leq n\leq 10,\quad 0\leq m\leq 1000,\quad 1\leq q\leq 10^5$。


    来源  感谢nodgd