logo AlgoBeat OnlineJudge
登录 注册

#101353. [BZOJ 1353] [Baltic2005]Maze

内存限制:162 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给出一个平行四边形的长与高。给出入口与出口。

对于四边形的每条边都有一种 ,非黑即白。

你要找出一条路径,走过的边黑白交替,且长度最短。

输入格式

第一行给出平行四边形的长 与高

第二行给出入口,出口坐标。

下面的字符矩阵代表这个平行四边形每条边的

输出格式

输出路径的最少长度。

样例

样例输入 #1

2 1
0 0 2 1
bb
nwwnw
bn

样例输出 #1

6

样例输入 #2

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

样例输出 #2

22

数据范围与提示

对于 的数据,满足

对于第一个数据:

对于第二个数据: