Problem 1172. -- 顽固的子弹

1172: 顽固的子弹

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 37  Solved: 13
[Submit][Status][Web Board]

Description

    ymy和lhl成功通过第二关之后,获得了一颗子弹,在他们面前出现了一群怪兽,ymy和lhl必须用子弹打倒他们。   

    ymy和lhl的子弹是无敌的,可以无限时间飞行,但是他们的子弹又十分顽固,ymy和lhl应该尽可能避免子弹拐弯。


    有一个n * m的方格矩阵,在某些方格内有怪兽存在(每个方格最多只有一个怪兽)。
子弹会从(x,y)出发(你可以为其选择一个方向 向上、向下、向左、向右作为初始方向,而不用计算在拐弯次数之内),要求子弹穿过所有的怪兽,并且拐弯次数最少,求出这个次数。


    拐弯指的是顺时针或者逆时针旋转90°或者180°(向左转、向右转、调头)

Input

第一行是两个正整数 n,m。

第二行是两个正整数 ,表示子弹出发的起点x,y

第三行到第n+3行,每行有m个数,数字为0/1,1表示这个位置有敌人, 0表示这个位置没有敌人。

Output

输出只有一个整数, 表示最小拐弯的次数。

Sample Input

3 4
1 1
0 1 1 0
0 1 1 0
0 1 1 0

Sample Output

3

HINT

n  < 7

m < 7

数据随机。

Source

[Submit][Status]