1839. 恶魔之城

小强生日就要到了，partychen 为了送给小强一个特别的礼物，决定到恶魔之城去偷走他们的镇城之宝：月亮之石。partychen 已经从江湖百晓生处得到了恶魔之城的地图。根据地图的描述，恶魔之城是一个标准的 $n \times m$ 大小的一个悬在空中的城堡，里面有可以走的路，也有一些陷阱，如果人踏入陷阱那么将被恶魔吃掉，如果不小心踏出这个城堡，那么就将尸骨无存。partychen 去城之前买了两个传送，第一个传送将把 partychen 安全的送往入口。第二个在拿到月亮之石的地方使用，安全的把 partychen 送回地面。由于时间紧迫，partychen 能力有限，希望天才的你帮助他计算一下从入口安全到达到月亮之石的所在地最快需要多少步。并且帮他算出应该怎么走步数最小。当然可能有很多种走法，你只要输出任意可行的一种就可以了。