当前没有测试数据。

走出迷宫

题目描述

小奇被困在了一个$N \times M$的迷宫中，迷宫的某些格子有着障碍，无法通过。出口在小奇的右方，因此小奇每一步只能向上、右、下三个方向行走。

由于某些神秘力量的作用，小奇和出口的位置会不断改变，同时迷宫的构造也有可能改变。

你要做的就是帮助小奇算出对于每种情况，小奇最少要走多少步才能到达出口。如果小奇无论怎样都无法走出迷宫，请输出$-1$。

输入格式

第一行包含三个正整数$N$，$M$，$Q$，分别表示迷宫的行数、列数、以及操作个数。

接下来$N$行，每行$M$个整数，每个整数为$0$或$1$——如果为$0$，表示这个格子中存在障碍，无法通行；如果为$1$，表示这个格子可以通行。

接下来$Q$行，每行第一个整数$opt$，表示操作的类型：

• 若$opt=1$，接下来会有$2$个整数$a$，$b$，表示改变迷宫坐标为$(a,b)$这一格的通行情况（第$a$行第$b$列），即如果原先可以通行，现在变为无法通行，反之亦然。
• 若$opt=2$，接下来会有$4$个整数$a$，$b$，$c$，$d$，表示询问当小奇的坐标为$(a,b)$，出口坐标为$(c,d)$时的答案。

输出格式

对于每个$opt=2$，输出一行一个整数，表示小奇到迷宫出口的距离。

数据范围与提示

• 对于$30\%$的数据，$N \leq 3$，$M \leq 5000$，$Q \leq 5000$；
• 对于$60\%$的数据，$N \leq 4$，$M \leq 10^{5}$，$Q \leq 3 \times 10^{4}$；
• 对于$100\%$的数据，$1 \leq N \leq 5$，$1 \leq M \leq 2 \times 10^{5}$，$1 \leq Q \leq 5 \times 10^{4}$，$1 \leq a,c \leq N$，$1 \leq b \leq d \leq M$。

样例

2 3 5
1 1 1
1 1 1
2 2 1 1 2
2 2 2 1 2
1 1 2
2 1 1 2 2
2 2 1 1 2

2
1
2
-1

3 5 10
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
2 2 1 2 2
1 1 5
2 2 3 3 4
2 3 1 3 2
1 1 1
2 3 1 1 4
2 3 1 3 3
1 2 2
2 3 2 1 2
2 3 2 2 5

1
2
1
5
2
-1
4