#P18298. Fractal Maze
Fractal Maze
Fractal Maze
用正方形格子和格子之间的墙构造一个迷宫。初始时只有一个格子,四周都有墙。然后进行 次扩张。
一次扩张的过程如下:取当前迷宫的四个完全相同的副本,拼成一个 的大正方形。四个副本均保持原有方向。站在新迷宫的中心,中心向右、上、左、下分别有一条隔开相邻副本的长墙。我们在其中三条墙上各开一个宽度为一格的通道,第四条墙保持完整。
每次扩张由四个整数 描述,分别对应从中心向右、上、左、下延伸的墙。恰好一个数为 ,表示该墙不开通道;其余三个正整数表示从中心开始数,在对应墙的第几个单位线段上开通道。例如, 表示紧挨中心的位置, 表示从中心数的第二段。

图中展示样例的三次扩张以及最终迷宫;小方向图标出了 的含义。
最终迷宫中任意两个格子之间恰好有一条简单路径。简单路径不会重复经过同一个格子。你需要回答 个询问:给出两个格子的坐标,求它们之间这条路径的长度。路径长度是移动到相邻格子的步数。
输入格式
第一行一个整数 ()。
接下来 行依次描述各次扩张。每行四个整数 ,恰有一个为 ,其余三个为正。第 次扩张之前迷宫的边长为 ,所以对应半墙上有 个可编号的位置,非零数均在 至 之间。
接下来一行一个整数 ()。
接下来 行,每行四个整数 $\mathrm{row}_A,\mathrm{col}_A,\mathrm{row}_B,\mathrm{col}_B$,表示两个格子的坐标,均在 至 之间。行从上往下编号,列从左往右编号。
输出格式
对每个询问输出一行一个整数,表示给定两格之间的简单路径长度。
样例
3
0 1 1 1
1 0 1 1
0 3 1 2
4
4 5 4 5
5 4 8 1
5 8 1 8
5 5 4 5
0
6
22
15