题面描述:

在这个问题中，小塔发现他的房间里进水了，水位不断上涨。他需要通过一些没有被水淹没的箱子移动，以安全地到达电源处。每个小方格的水位上升与箱子的高度有关，只有当水位低于箱子高度时，小塔才能通过该格。输入给出初始水深、房间的格局以及小塔和电源的位置，输出则是小塔从起点到电源的路径长度和每一步的位置坐标。如果无法到达电源，小塔则留在原地。通过这个问题，我们可以帮助小塔设计一条安全的路线，以确保他能顺利关闭电源。

思路:高维bfs

考虑记录状态:(x,y,step) 代表在位置x,y并且已经走了step步状态下是否合法。

$fa[x][y][step]$ 记录这个状态下的上一步是哪里来的。

题目内容

小明正值班，突然发现他所在的屋子进水了，水面一直上涨，考虑到可能有电器暴露在水中，小明想通过尚未被水淹没的箱子达到电源处，关闭电源。假设电源和小明所处的位置都比较安全，不会被水淹没。已知屋子为矩形，可划分为大小相当的小方格，小明的位置，电源，箱子都正好在小方格的正中间，覆盖整个方格；小明每单位时间可以从一个小方格移动到相邻的处在同一行或者同一列的另一小方格。为了安全小明只能移动到没有被上涨的水面淹没的小方格，箱子的高度不一，所在方格被水淹没的时间取决于方格内箱子的高度

水面每单位时间上涨$1$，如果此时箱子的高度小于或者等于水面的高度，则被淹没。

请帮小明设计一条路线到达电源处，如果没有这样的路线，则小明应该待在原地。

输入描述

第一行：开始时水的深度

第二行：用空格隔开的两个数字，第一个为屋子的长，对应余下输入的行数，第二个为屋子的宽，对应余下输入各行和个数

从第三行开始，描述屋子内小方格的布局。用非$0$数字代表箱子的高度，$0$代表没有箱子，$s$代表小明的位置，t代表电源位置

输出描述

第一行输出一个$m$ , 代表路径长度

接下来$m$ 行，每行一个坐标$(x_i,y_i)$ 代表第$i$步的位置

样例1

输入

0
4 4
s 1 3 5
2 3 2 4
2 4 4 5
3 5 5 t

输出

1
0 0

说明

无法安全到达电源位置，只能呆在原地$s$所在位置

样例2

输入

0
4 4
s 1 2 5
2 3 2 4
2 4 4 5
3 5 7 t

输出

7
0 0
1 0
1 1
2 1
3 1
3 2
3 3

说明

输入：第一行表示开始水面深度为$0$，第二行表示屋子为$4*4$的方格；如果方格坐标从$1$开始，则小明在第$1$行第$1$列，电源在第$4$行第$4$列；

输出：输出了从小明所在位置$s$到电源所在位置$t$以及路径上的箱子高度

注意:如果有多个方案，输出任意一个合法的移动方案即可。