4. 大哈的变换迷宫
XJOI - 题目ID：8579必做题100分
最新提交：
Wrong Answer
10 分
历史最高：
Wrong Answer
10 分
时间限制: 1000ms
空间限制: 524288kB
题目描述
【题目描述】
大哈已经是个成年人了，网页游戏在他当年还是风靡一时。他记忆中有这么一款游戏。
角色一开始在迷宫的(1,1)处，最终要到达(n,n)的位置，迷宫中有一些障碍物，障碍不能走。同时迷宫中有些点是彩色点，彩色点的颜色按照这个点的颜色序列每秒变换一次，变完了又会循环，比如这个颜色点会这么变，“1 2 4”,所以它第一秒是1，第二秒是2，第三秒是4，第四秒又是1，依次往复。当你到达彩色点的时候，你可以选择把他当普通点直接走上去，也可以选择在彩色点传送，传送到任意一个此时和它颜色相同的彩色点上，传送不需要时间。大哈可以往上下左右走，走一格花费1秒，他也可以选择不动，等一秒，因为说不定等一秒，下一步就可以直接传送了。大哈现在已经学过一些算法了，他想知道到达(n,n)的最短时间是多少？
【输入格式】
第一行，一个整数n
接下来n行，每行n个整数，用空格隔开。每个整数是0或者1，0表示空地，1表示障碍物。保证起点和终点都是0
接下来1行，一个整数t，表示彩色格子的数量
接下来t行，每行第一个和第二个整数xi和yi表示这个彩色格子的坐标；第三个整数mi，表示第i个彩色格子的颜色序列长度，后面跟着mi个整数，表示当前这个彩色点的颜色变换顺序
【输出格式】
一个整数，表示到达终点的最短时间，如果不能到达终点，输出-1.
【样例输入】
5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 1 1
0 0 1 0 0
3
2 2 3 1 2 3
3 4 5 1 2 1 2 4
5 4 4 5 5 5 4
【样例输出】
21
【数据范围】
n<=1000, t<=10, 颜色种类不超过10，mi不超过10