题目内容

在一条河流中有一座小岛，地图可以表示为一个 $r$ 行 $c$ 列的方格矩阵。矩阵中的每个格子只有两种类型：0 表示水域，1 表示陆域。小鲤鱼被困在岛上，起点是 $(sx, sy)$。如果起点本身是陆域，它无法开始移动，直接视为逃生失败。

小鲤鱼每次只能从一个水域格子移动到上下左右四个相邻格子之一，而且目标格子也必须是水域。它不能斜着移动，也不能进入陆域。只要它到达矩阵四条边界上的任意一个水域格子，就视为成功离开小岛。

在能够成功逃生的所有路线中，需要按以下优先级选出最优路线：

• 首先，选择移动步数最少的路线，步数不包括起点。
• 如果有多条路线步数相同，选择终点坐标更小的路线。终点的坐标比较时先比较行号，行号更小者优先；若行号相同，再比较列号，列号更小者优先。
• 如果步数和终点坐标都相同，则选择整条路线上所有点的行号之和更小的路线；若行号之和仍相同，则选择整条路线上所有点的列号之和更小的路线。
• 不需要处理上述所有指标全部相同但路径不同的特殊情况。

约束条件

行数 r 的范围为 $3 \le r \le 20$；列数 c 的范围为 $3 \le c \le 30$。起点坐标满足 $0 \le sx < r$ 和 $0 \le sy < c$。地图中每个格子只可能是 0 或 1。

输入描述

第一行包含两个整数 r 和 c，表示地图的行数和列数。

第二行包含两个整数 sx 和 sy，表示小鲤鱼的起始坐标。

接下来 r 行，每行包含 c 个整数，每个整数为 0 或 1，按行描述地图。

输出描述

如果无法到达任何一个边界水域，则输出 -1。

否则，第一行输出一个整数 d，表示最优路线的移动步数，不计入起点。随后输出 $d+1$ 行，每行两个整数，表示从起点到终点的最优路线依次经过的坐标，其中第一行必须是起点。

样例1

输入

5 5
1 1
1 1 1 1 1
1 0 0 1 0
1 1 0 1 0
1 1 0 0 0
1 1 1 1 1

输出

5
1 1
1 2
2 2
3 2
3 3
3 4

说明

从起点 (1, 1) 出发，上、下、左三个相邻格子都是陆域，只能向右进入 (1, 2)。随后需要绕过陆域，依次经过 (2, 2)、(3, 2)、(3, 3)，最终到达右边界水域 (3, 4)。

共移动 5 步，因此输出该路径。

样例2

输入

3 3
1 1
0 0 0
0 1 0
0 0 0

输出

-1

说明

起点 (1, 1) 在地图中的值为 1，属于陆域。由于起点本身是陆域时无法开始移动，因此无法逃生，输出 -1。

样例3

输入

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

输出

0
0 1

说明

起点 (0, 1) 是水域，且行号 0 是地图的上边界。它本身已经满足到达边界水域的条件，因此无需移动，步数为 0，路径只包含起点。