#2053. 「BJOI2019」送别

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

法珞是个怕黑的女孩子。

傍晚了,法珞所参加的学术会议早已散会。黎瑟也下了课过来接法珞回火车站。

但是教学楼里突然断电了,法珞陷入了一片漆黑之中。

好在黎瑟已经到了教学楼的同一层。

然而由于教学楼的结构过于复杂,她们已经记不起教学楼的具体结构了。 黎瑟学校的教学楼每层的结构都非常工整。

形式化地说,教学楼的一层的平面结构可以画在二维平面上以 (0,0) 为左上角顶点, (n,m) 为右下角顶点的子矩形(记为 (0,0) - (n,m) 的矩形)里,这个子矩形的四条边是教学楼的楼体(或者说是四段已知一定存在的墙)。

请注意,本题中的坐标系和普通的平面直角坐标系不同, (0,0) 是左上角的顶点而 (n,m) 是右下角的顶点。 (i,j) 表示的是第 i+1 行第 j+1 列的顶点而不是横坐标为 i 纵坐标为 j 的顶点。

每一段墙(无法通过的部分)是一条端点为 (i,j) (i',j') 的线段,记作 (i,j) - (i',j') 的墙,其中 |i-i'| + |j-j'| =1 i,i' [0,n] 中的整数, j,j' [0,m] 中的整数(每当我们之后使用 (i,j) - (i',j') 的记法,我们都保证满足上述所有条件)。

法珞知道,对于这种结构,有一种办法可能让她找到黎瑟:法珞用左手扶住墙,手臂和墙面垂直,保持这个状态向前方走,在转弯处也保持左手一直扶墙的状态。按照这个方法她就可以环绕一周,可能与黎瑟相遇。

法珞一开始会给你需要维护的初始的(这层楼的)结构,之后会给你 q 个请求。

  • 操作 1 :读入格式形如 1\ x_0\ y_0\ x_1\ y_1 :法珞请求在当前结构里添加一段 (x_0, y_0) - (x_1, y_1) 的墙,保证此前这段墙不存在且这段墙不在 (0, 0)-(n, m) 的子矩形的四条边上。

  • 操作 2 :读入格式形如 2\ x_0\ y_0\ x_1\ y_1 法珞请求在当前结构里删除一段 (x_0,y_0) - (x_1,y_1) 的墙,保证此前这段墙存在且这段墙不在 (0,0) - (n,m) 的子矩形的四条边上。

  • 操作 3 :读入形如 3\ x_0\ y_0\ x_1\ y_1\ d_0\ x_2\ y_2\ x_3\ y_3\ d_1 :法珞当前在 (x_0,y_0) - (x_1,y_1) 的墙的中点位置 (\frac{x0+x1}{2},\frac{y_0 + y_1}{2}) d_0 是一个 [0,1] 中的整数,用来描述法珞在墙的哪一侧, d_0 = 0 代表法珞在墙的左方/上方, d_0 = 1 代表右方/下方。黎瑟当前在 (x_2,y_2) - (x_3,y_3) 的墙的中点位置 (\frac{x2+x3}{2},\frac{y_2+y_3}{2}) d_1 的格式和 d_0 相同。保证 (x_0,y_0) - (x_1,y_1) (x_2,y_2) - (x_3,y_3) ) 这两段墙存在,且法珞和黎瑟的位置都落在 (0,0) - (n,m) 的子矩形的内部。求法珞按照题目所述的方法找到黎瑟要走过多少长度( (i,j) - (i',j') 这段墙的长度为 1 ,半段墙(由于起点和终点都在墙的中点处)的长度是 \frac{1}{2} )。

输入格式

输入共 2n+q 行。

第一行三个整数 n,m,q ,意义如题目中所示。

接下来的 n 行,每行 m-1 [0,1] 中的整数,第 i 行第 j 列的整数为 1 表示 (i,j) - (i-1,j) 这一段有墙,为 0 则表示 (i,j) - (i - 1,j) 这一段没有墙。

接下来的 n-1 行,每行 m [0,1] 中的整数,第 i 行第 j 列的整数为 1 表示 (i,j) - (i,j-1) 这一段有墙,为 0 则表示 (i,j) - (i,j-1) 这一段没有墙。

接下来的 q 行,每行一个操作,格式如题目中所示。

输出格式

对于每个询问,输出法珞按照题目所述的方法找到黎瑟要走过多少长度,如果法珞按照题目所述的方法无法找到黎瑟则输出 \mathbf{-1}

样例

样例输入 1

3 3 4
0 0
1 0
0 0
1 0 1
0 0 1
3 3 0 3 1 0 0 3 1 3 0
1 2 1 2 0
2 1 0 1 1
3 2 2 2 3 1 1 2 1 3 0

样例输出 1

11
16

样例解释 1

leave1.png

上图是样例输入中第一次询问的法珞的行走方案,在行走过程中法珞的左手必须贴住墙。

数据范围与提示

对于 10\% 的数据, 5\le n, m\le 50, 1\le q\le 2\times 10^3

对于另外 30\% 的数据,没有 1 操作。

对于另外 30\% 的数据,保证在任意时刻若法珞和黎瑟站在任意输入格式中合法的位置,法珞都可以和黎瑟相遇。

对于 100\% 的数据, 5\le n, m\le 500, 1\le q\le 2\times 10^5