#P1374. 进攻幽暗城

进攻幽暗城

题目背景

由于震惊海内外的 “愤怒门投毒事件” 的发生,部落为了对抗皇家药剂师协会的叛乱,所有的外交工作完成后,部落大酋长萨尔带领着小 A 穿过传送门到达幽暗城平叛。

题目描述

幽暗城的地图是一个 n×mn \times m0101 串。ai,j=1a_{i, j} = 1 时表示 (i,j)(i, j) 的位置是障碍,无法通过;ai,j=1a_{i, j} = 1 时表示 (i,j)(i, j) 的位置可以进入。

小 A 与萨尔的初始位置是 (x1,y1)(x_1, y_1),而恐惧魔王的初始位置是 (x2,y2)(x_2, y_2)。小 A 的目标就是到达恐惧魔王的位置。

萨尔会按照一个特定的路线行走,该路线是一个数字串,由 040 \sim 4 组成。

ii 秒,若数字串第(imodi \bmod {}数字串的长度)位等于 00,则表示这一秒萨尔将会原地不动;
等于 11,则表示这一秒萨尔会向上走一格;
等于 22,则表示这一秒萨尔会向下走一格;
等于 33,则表示这一秒萨尔会向左走一格;
等于 44,则表示这一秒萨尔会向右走一格。

若萨尔将要移动的位置是墙或者超出迷宫的范围,则萨尔会原地不动。恐惧魔王也是这样。(换句话说,你可以认为如果将数字串是重复无限次,第 ii 秒就是字符串第 ii 位)

小A每秒可以选择从上下左右四个方向中选择一个方向,朝那个方向走一格,前提是那个位置不是墙并且没有超出迷宫的范围;或者原地不动。不过,由于幽暗城的诡异环境,小 A 只能持续脱离萨尔的光环 ss 秒,若超过 ss 秒小 A 则会死亡。光环的有效半径为 dd ,表示当小 A 与萨尔之间的距离 (xxx)2+(yyy)2\sqrt{(x-xx)^2+(y-yy)^2} 小于等于 dd 时小 A 才能受到萨尔光环的效果。若小 A 脱离萨尔的光环又重新进入光环有效区域,则再次离开光环时持续时间归零重记。

小 A 想知道最少需要几秒他才能到达恐惧魔王所在的位置。

输入格式

第一行四个数 n,m,s,dn,m,s,d

接下来的 nn 行,每行 mm 个数(0011),之间没有空格,表示幽暗城的地图。

接下来的一行四个整数,x1,y1,x2,y2x_1,y_1,x_2,y_21x1,x2n1 \le x_1,x_2 \le n1y1,y2m1 \le y_1,y_2 \le m)。

接下来的一行是一个数字串,表示萨尔的移动方式。

接下来的一行是一个数字串,表示恐惧魔王的移动方式。

输出格式

一行一个整数,表示需要最少的时间。

3 4 7 3
1010
0000
0101
1 2 3 3
0132401
12131

3

提示

【题目来源】

kiro 原创

【数据范围】

对于 100%100\% 的数据,1n,m501 \le n,m \le 500s10000 \le s \le 10000d1000 \le d \le 10011 \le 数字串长度 100 \le 10000 \le 答案 100 \le 100