#P1353. [Baltic2005]Maze

[Baltic2005]Maze

[BalticOI 2005] Maze

题目描述

给出一个平行四边形的长与高. 给出入口与出口,对于四边形的每条边都有一种Color,非黑即白. 你要找出一条路径,走过的边黑白交替,且长度最短。保证存在这样的路径。首次移动可以经过黑边或白边。

输入格式

第一行给出平行四边形的长与高.且值在[1,500] 第二行给出入口,出口坐标. 接下来有 2H+12H+1 行。奇数行有 WW 个字符,表示水平边;偶数行有 2W+12W+1 个字符,依次表示连接相邻两行顶点的竖边与斜边。字符 n 表示不可经过,w 表示白边,b 表示黑边。平行四边形顶点使用坐标 0≤x≤W,0≤y≤H0\le x\le W,0\le y\le H,三类无向边连接 (x,y)(x,y) 与 (x+1,y)(x+1,y)、(x,y+1)(x,y+1)、(x−1,y+1)(x-1,y+1)。入口与出口均为上述顶点。

输出格式

输出路径的最少长度

样例 #1

样例输入 #1

2 1
0 0 2 1
bb
nwwnw
bn

样例输出 #1

6

样例 #2

样例输入 #2

5 4
0 2 5 2
nnbnn
nnnwwbwnnnn
nbbbn
nnwbwwbwwnn
bwwww
nnbwbbwwbnn
nwwwn
nnnnbwbbnnn
nnwnn

样例输出 #2

22

提示

对于第一个数据:

(0, 0) -> (1, 0) -> (0, 1) -> (1, 1) -> (1, 0) ->(2, 0) -> (2, 1)

对于第二个数据:

(0, 2) -> (1, 2) -> (1, 1) -> (2, 1) -> (2, 0) ->

(3, 0) -> (3, 1) -> (3, 2) -> (4, 1) -> (3, 1) ->

(3, 0) -> (2, 0) -> (2, 1) -> (1, 1) -> (1, 2) ->

(1, 3) -> (2, 3) -> (2, 4) -> (3, 4) -> (3, 3) ->

(4, 3) -> (4, 2) -> (5, 2)