#P18298. Fractal Maze

Fractal Maze

Fractal Maze

用正方形格子和格子之间的墙构造一个迷宫。初始时只有一个格子,四周都有墙。然后进行 nn 次扩张。

一次扩张的过程如下:取当前迷宫的四个完全相同的副本,拼成一个 2×22\times2 的大正方形。四个副本均保持原有方向。站在新迷宫的中心,中心向右、上、左、下分别有一条隔开相邻副本的长墙。我们在其中三条墙上各开一个宽度为一格的通道,第四条墙保持完整。

每次扩张由四个整数 r,u,l,dr,u,l,d 描述,分别对应从中心向右、上、左、下延伸的墙。恰好一个数为 00,表示该墙不开通道;其余三个正整数表示从中心开始数,在对应墙的第几个单位线段上开通道。例如,11 表示紧挨中心的位置,22 表示从中心数的第二段。

原题迷宫扩张示意图

图中展示样例的三次扩张以及最终迷宫;小方向图标出了 r,u,l,dr,u,l,d 的含义。

最终迷宫中任意两个格子之间恰好有一条简单路径。简单路径不会重复经过同一个格子。你需要回答 qq 个询问:给出两个格子的坐标,求它们之间这条路径的长度。路径长度是移动到相邻格子的步数。

输入格式

第一行一个整数 nn(1≤n≤301\le n\le30)。

接下来 nn 行依次描述各次扩张。每行四个整数 r,u,l,dr,u,l,d,恰有一个为 00,其余三个为正。第 ii 次扩张之前迷宫的边长为 2i−12^{i-1},所以对应半墙上有 2i−12^{i-1} 个可编号的位置,非零数均在 11 至 2i−12^{i-1} 之间。

接下来一行一个整数 qq(1≤q≤10001\le q\le1000)。

接下来 qq 行,每行四个整数 $\mathrm{row}_A,\mathrm{col}_A,\mathrm{row}_B,\mathrm{col}_B$,表示两个格子的坐标,均在 11 至 2n2^n 之间。行从上往下编号,列从左往右编号。

输出格式

对每个询问输出一行一个整数,表示给定两格之间的简单路径长度。

样例

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