题目描述

在一个$X \times Y$的矩形棋盘上放置着一个立方体，立方体的边长与棋盘单元格的边长相等。每一步操作中，立方体可以沿其边滚动，移动到垂直或水平相邻的单元格。某些单元格之间可能存在作为障碍物的墙，立方体不能滚过这些障碍物，也不能滚出棋盘。

你需要确定将立方体从初始坐标$(A, B)$移动到目标坐标$(C, D)$所需的最小步数，且最终位置的上表面必须与初始位置的上表面相同。

所有输入均为正整数，满足$2 \leq X, Y \leq 10$。

输入格式

第一行包含两个用一个或多个空格分隔的整数$X$和$Y$。类似地，第二行包含初始坐标$A$和$B$，第三行包含目标坐标$C$和$D$。随后可能包含关于墙的信息：

• 以单独一行的符号v开头，其后若干行每行包含一对整数$(M, N)$，表示在单元格$(N, M)$和$(N+1, M)$之间存在垂直墙（竖直方向分隔左右单元格）。
• 以单独一行的符号h开头，其后若干行每行包含一对整数$(M, N)$，表示在单元格$(N, M)$和$(N, M+1)$之间存在水平墙（水平方向分隔上下单元格）。

输出格式

输出唯一一行，包含所需的最小步数。若无法完成移动（满足最终坐标和上表面条件），则输出no。

输入数据 1

10 2  
1 1  
10 1  
v  
2 1  
6 2  
h  
4 1  

输出数据 1

11  

题目来源

Ural Collegiate Programming Contest 1998