easy playing sokoban problem

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

    Alice 很喜欢玩推箱子的游戏,但是推箱子太难了,Alice就去求助Bob,Bob为了让Alice有跟好的的游戏体验,就发明了一个新的推箱子玩法,即可以直接让箱子自己移动。
     游戏具体玩法是这样的,给你一个n行m列大小的地图,和两个箱子A,B和需要移动到对应的位置C,D(必须把A移动到C,B移动到D)每一秒你都可以任意选择一个的箱子移动到它的相邻位置。你需要计算出是否可以完成这个游戏和最小需要多少步。

Input

     第一行两个正整数n,m (1<=n,m<=16)

     第二行四个正整数x1,y1,x2,y2,分别表示两个箱子的位置(1<=x1,x2<=n,1<=y1,y2<=m)

     第三行四个正整数x1,y1,x2,y2,分别表示需要移动到的位置(1<=x1,x2<=n,1<=y1,y2<=m)

     第四行一个整数k,表示有多少个格子是墙(1<=k<=n*m)

     接下来是k行,每行两个整数xi,yi 表示第i个墙所在的位置

Output

如果可以完成,输出一个整数表示完成游戏需要的最小步数

如果不能完成 输出"-1"(不包括引号)

Sample Input

3 3
1 1 2 1
1 3 2 3
1
2 2

Sample Output

6

Hint

Source

7989