#1353. [Baltic2005]Maze

题目描述

给出一个平行四边形的长与高. 给出入口与出口,对于四边形的每条边都有一种Color,非黑即白. 你要找出一条路径,走过的边黑白交替,且长度最短

输入格式

第一行给出平行四边形的长与高.且值在[1,500] 第二行给出入口,出口坐标. 下面的字符矩阵代表这个平行四边形每条边的Color

输出格式

输出路径的最少长度

样例

样例输入

inupt 1  

2 1  

0 0 2 1  

bb  

nwwnw  

bn  

  

input 2  

5 4  

0 2 5 2  

nnbnn  

nnnwwbwnnnn  

nbbbn  

nnwbwwbwwnn  

bwwww  

nnbwbbwwbnn  

nwwwn  

nnnnbwbbnnn  

nnwnn

样例输出

output 1  

6  

  

output 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)