1007. push!

**单点时限: **2.0 sec

**内存限制: **256 MB

Mr. Schwarz was a famous powerful pro wrestler. He starts a part time job as a warehouseman. His task is to move a cargo to a goal by repeatedly pushing the cargo in the warehouse, of course, without breaking the walls and the pillars of the warehouse.

There may be some pillars in the warehouse. Except for the locations of the pillars, the floor of the warehouse is paved with square tiles whose size fits with the cargo. Each pillar occupies the same area as a tile.

Initially, the cargo is on the center of a tile. With one push, he can move the cargo onto the center of an adjacent tile if he is in proper position. The tile onto which he will move the cargo must be one of (at most) four tiles (i.e., east, west, north or south) adjacent to the tile where the cargo is present.

To push, he must also be on the tile adjacent to the present tile. He can only push the cargo in the same direction as he faces to it and he cannot pull it. So, when the cargo is on the tile next to a wall (or a pillar), he can only move it along the wall (or the pillar). Furthermore, once he places it on a corner tile, he cannot move it anymore.

He can change his position, if there is a path to the position without obstacles (such as the cargo and pillars) in the way. The goal is not an obstacle. In addition, he can move only in the four directions (i.e., east, west, north or south) and change his direction only at the center of a tile.

As he is not so young, he wants to save his energy by keeping the number of required pushes as small as possible. But he does not mind the count of his pedometer, because walking is very light exercise for him.

Your job is to write a program that outputs the minimum number of pushes required to move the cargo to the goal, if ever possible.

The input consists of multiple maps, each representing the size and the arrangement of the warehouse. A map is given in the following format.

w h

d11 d12 d13 … d1w

d21 d22 d23 … d2w

. . .

dh1 dh2 dh3 … dhw

The integers w and h are the lengths of the two sides of the floor of the warehouse in terms of widths of floor tiles. w and h are less than or equal to 7. The integer dij represents what is initially on the corresponding floor area in the following way.

0: nothing (simply a .oor tile)

1: a pillar

2: the cargo

3: the goal

4: the warehouseman (Mr. Schwarz)

Each of the integers 2, 3 and 4 appears exactly once as dij in the map. Integer numbers in an input line are separated by at least one space character. The end of the input is indicated by a line containing two zeros.

For each map, your program should output a line containing the minimum number of pushes. If the cargo cannot be moved to the goal, -1 should be output instead.

Input

5 5 0 0 0 0 0 4 2 0 1 1 0 1 0 0 0 1 0 0 0 3 1 0 0 0 0 5 3 4 0 0 0 0 2 0 0 0 0 0 0 0 0 3 7 5 1 1 4 1 0 0 0 1 1 2 1 0 0 0 3 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 6 6 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 4 0 0 0 0 0 0 0

Output

5 -1 11 8

不限期开放

1001. Problem A+B (Big Integer)
1002. 线性同余方程
1003. Expected Allowance
1004. Joseph
1005. Alex and Prime
1006. Halloween treats
1007. push!
1008. 游戏
1009. Drainage Ditches
1010. Playing With Cubes
1011. 你是ACM吗？
1012. Asteroids
1013. The Bottom of a Graph
1014. 路由器
1015. 人民的救星
1016. A X B
1017. A/B (Big Integer)
1018. 握手
1019. 母牛的故事
1020. Hanoi Tower III
1021. Hanoi Tower II
1022. Tr A
1023. Hanoi Tower IV
1024. Max Sum
1025. 汽车加油
1026. Wavelet Compression
1027. Best Cow Line
1028. easy to do DP
1029. The Tower of Babylon
1030. Loan Scheduling
1031. Apple Catching
1032. Nested Dolls
1033. ZigZag
1034. I-Keyboard
1035. A Knight's Journey
1036. Sticks
1037. 恶魔之城
1038. Kryie
1039. Prime Path
1040. 剩余定理
1041. 整数幂
1042. A-B(Big Integer)
1043. Guarding the Farm
1044. 数塔II
1045. 数塔III
1046. 数塔IV
1047. 糖果
1048. 集合运算
1049. 统计字母频率
1050. 达到回文数
1051. 小强的生日
1052. 成绩排序
1053. 华师大卫星照片
1054. 路由结点
1055. 统计字符串个数
1056. 符号方程求解
1057. 排序去重
1058. 内存显示
1059. 一元多项式乘法
1060. 围栏
1061. 统计特定字串模式的个数
1062. 进制转换
1063. 母牛生小牛
1064. 查询Ⅱ
1065. 查询
1066. 统计
1067. 绝对值排序
1068. 成绩统计
1069. 工程
1070. 染气球
1071. 庆祝迎评成功
1072. sunny的烦恼
1073. 起床
1074. 判断两个数是否相等
1075. 小强斗旺财I
1076. 强盗
1077. 表达式
1078. Way to Escape
1079. 简单迷宫问题
1080. Easy Game 1
1081. 考新郎
1082. I want out of that maze!
1083. 小强过桥
1084. WYI
1085. 放书
1086. 强大的lwc
1087. Seamild的作业I
1088. 计算n!右端0的个数(II)
1089. 孤独数
1090. 比赛排名
1091. 拥塞的城市
1092. 小强的生日
1093. 十六进制加法
1094. 天黑请闭眼
1095. 加密1
1096. 自修室
1097. 整数的拆分
1098. 4个值的和为0
1099. 最小向量点积
1100. 棋盘上的车
1101. 最小等待时间
1102. sunny的游戏
1103. sunny的队列
1104. sunny的密码
1105. sunny购物
1106. 雷电
1107. COIN COLLECTOR

通知

比赛状态发生变化，点 OK 刷新。

通知