Skip to content

1028: 采购

题目

题目描述

skytim是伟大帝国UDF的首脑。作为一国的领袖,skytim很早就认识到一国的交通对经济建设的重要性。于是他要求UDF国内的建筑排成m*n的网络,道路建设在建筑的上方,并且每条道路都连接着两个有公共边的建筑。如下图所示:

这天是UDF国建国110周年纪念日,skytim正在主持盛大的阅兵式。随着“同志们好!”“首长好!”的声响此起彼伏,skytim的手机突然响了,是他的夫人Cyning打来的。

“skytim你早饭煮烂了,快给我回来!”

“啊?我还在阅兵呢!”

“我不管你现在在哪里,现在马上给我回来!”

“嗯,我现在马上回去!”

“回来记得顺路帮我买一把油纸伞。我要撑着它走过那条雨巷。好想知道成为戴望舒笔下那个丁香一样的结着愁怨的姑娘是一种怎样的体验。”

“行行行,随你。”

为了及时完成夫人的任务,skytim希望能够走一条最短的经过伞店的路径回家。但遗憾的是有些建筑正在施工,和它连着的道路都不能走。好在skytim早就对自己国家的地图烂熟于心,请你协助他找到最短的路径。

输入格式

输入第一行有两个整数n,m,表示地图的规模。

接下来m行每行n个数字,表示该建筑的状态。其中:

  • 0表示普通建筑,可以经过。
  • 1表示正在施工中的建筑,不可以经过。
  • 2表示skytim阅兵的位置。
  • 3表示skytim和Cyning的家。
  • 4表示伞店。

输出格式

输出一个整数,表示skytim最少需要移动的距离。

样例输入

8 4 4 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 2 1 1 3 0 4 0 0 0 0 4 1 1 1 0

样例输出

11

数据范围

对于$40\%$的数据,$1 \le n,m \le 10$;

对于$100\%$的数据,$1 \le n,m \le 1000$.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!