在 n×m 个点组成的地图上，每一个点可以用坐标 (x, y)（1≤x≤n,1≤y≤m）来表示。地图上爬来了一只小蚂蚁，小蚂蚁从地图边界上的一点出发（形式化地说，从 (x0​,y0​) （x0​=1或x0​=n或y0​=1或y0​=m ）出发），在地图上留下了一条由 # 给出的路径，并在地图中的某个点停止运动。

小蚂蚁可以在每一步中选择以下 4 种方式之一移动，但它不能移动到地图之外（即移动完后的坐标依然合法），我们定义小蚂蚁在一步中能够移动到的位置集合为“相邻位置”：

•  (x,y)→(x+1,y)
•  (x,y)→(x,y+1)
• (x,y)→(x−1,y)
• (x,y)→(x,y−1)

小蚂蚁的移动路径非常特殊，移动路径并不会相交，也就是说，从路径的起点出发，路径的每一个点的相邻位置中至多存在一个在路径上的、且之前没有走到过的点。 给出小蚂蚁路径的初始位置，请你帮助小蚂蚁还原出对应的路径。

输入格式

第一行为 4 个整数n,m,x0​,y0​ ，表示地图的大小和路径的起始位置 (x0​,y0​) ，保证1≤n,m≤50 ， (x0​,y0​) 在地图的边界上。
接下来给出一个 n×m 的字符串矩阵，矩阵中仅有 # 和 _ 两种字符，# 表示路径中的痕迹，而 _ 表示空地。保证给出的地图以及给出的路径满足描述中的所有性质。

输出格式

第一行输出一个整数 ans，即路径的长度。
接下来有 ans行，每行包含两个整数 xi​,yi​ ，表示路径中的每个点。

测试样例

Input
3 3 1 1
#__
___
___
Output
1
1 1

解题思路

根据题意，输入数据包括一个二维数组表示迷宫（地图），#代表可以通过区域，_代表不可通行区域，小蚂蚁的移动轨迹是上下左右，但是小蚂蚁不能走回头路。

小蚂蚁的初始位置是x、y，能够移动的位置只能是(x,y-1、(x,y+1)、（x+1，y)、（x-1，y),这里面的一个位置，小蚂蚁在走下一步时，需要判断这几个位置是否合法，当这几个位置都不合法时，说明小蚂蚁走到了终点，需要退出了。

还需要对小蚂蚁走过的位置进行标记，在判断下一步将要走的位置时，如果当前位置已经走过了，就属于不合法的位置。

根据上述题意分析，C/C++ 代码实现上就不会有太大的挑战了。如果有疑问或者需要源码，可通过公众号与我联系。