#6683. 逃离实验室

逃离实验室

Background

🐂大哥作为一名间谍,他成功混入了ACM实验室,并夺得了一块xcpc的金牌。但同时🐂大哥也触发了警报,现在他需要尽快逃离ACM实验室

Description

🐂大哥可以向上下左右四个方向瞬移,每一次瞬移只能传送2的幂的距离,并且在瞬移的路径上不能有障碍物

ACM实验室整体是一个n*m的矩形,而🐂大哥现在正处于(1,1)坐标,而出口在(n,m)坐标

求🐂大哥至少要瞬移几次才能到达出口,由于ACM实验室可能在警报中启动部分障碍物,所以当🐂大哥无法抵达出口时输出"hiahia~"

Format

Input

第一行两个正整数n和m,10<n,m<2e3

接下来n行,每行m个数字,数字只由0或1组成,其中0代表无障碍物,1代表有障碍物

Output

一个整数,表示抵达出口的最少的瞬移次数,如果无解输出"hiahia~"

Samples

8 3
0 1 1 
0 0 0 
1 0 0 
0 0 0 
0 0 0 
0 1 0 
0 0 0 
1 1 0 

4

Limitation

1s, 1024KiB for each test case.