F : 漏油的小汽车

Progress Bar

时间限制:1 Sec 内存限制:128 MiB

提交


题目描述

JK(就是群主)在发财之后花了66w买了一辆某豪华品牌的轿跑,但是他并不知道这辆车的发动机存在隐患,会漏油。JK平时也就是觉得这车油耗高,毕竟这车高级,油耗高也很正常。一天,JK开车去爬雪山,突然开在路上雪越下越大,车陷在了雪堆里面,因为四周都是高山,JK不知道自己在哪里,突然JK发现自己的车后面有一条很长的油迹,于是救援队就循着JK的豪华汽车留下的油迹开始寻找JK。


JK比较聪明,他是优先按照上下右左的优先顺序的最短的路径到当前位置的。给你到JK之间的地图,现在让你找到JK的漏油路径,并且标注在地图上。

 

什么叫上下右左的优先顺序,也就是JK在找到这条最短路径的时候会优先选择往上走其次是向下走,然后是向右走,最后向左走,并且JK不会走回头路。地图被简化为0,1组成的二维数组,0表示当前可以走,1表示不可走。

救援队在地图的左上角,JK在地图的右下角。

输入描述

第一行m n,给出地图的大小 $m \cdot n$ , $m$ 为行数,$n$ 为列数。 $2 \leq m,n \leq 100$

接下来 $m$ 行每 $n$ 个元素就是地图。

输出描述

用#标记出这个地图里面JK的油迹

样例输入

3 3
011
000
110

样例输出

#11
###
11#

来源

JK WIT第二届程序设计竞赛(网络赛)