0
已解决
中级光能
1099 蚂蚁
经验值：800 时间限制：1000毫秒
合肥市第27届信息学竞赛
不许抄袭，一旦发现，直接清空经验！
题目描述 Description
蚂蚁在回家路上，他的任务自然是回家。蚂蚁在一个w*h个方格的地图上。每秒钟他能向上下左右四个方向移动一格，但不能离开地图。由于蚂蚁体能有限，每秒钟他要消耗1点HP, 刚开始时他有满HP6点。他可以沿路通过进食来补满HP（即6点），只要他走到有食物的格子，他不需要任何时间即可进食完毕。一个格子上的食物量对于小蚂蚁来说是庞大的，只要他愿意，每次经过这个格子都有吃不完的食物。
一旦蚂蚁的HP降到0，他将死去，就算到了某个有食物的格子才死去，他也不能通过进食补满HP。即使再家门口死去，他也不能算完成任务回到家中。
地图上有5种格子：
数字0：表示障碍物，蚂蚁不能走到这个格子上，更不能跨越。
数字1：表示空地，蚂蚁可以自由行走
数字2：表示蚂蚁出发点，他也是一片空地。
数字3：表示蚂蚁的家。
数字4：表示有食物在上面的空地。
你能告诉蚂蚁先生他能否安全回家，如果能，最短需要多长时间呢？
输入描述 Input Description
第一行，表示宽w和长h。
下面h行，每行w个数字来描述地图。
【数据规模】
0<w,h<9
输出描述 Output Description
一行，若蚂蚁不能回家，输出-1,否则输出蚂蚁回家所需最短时间。
样例输入 Sample Input
3 3 2 1 1 1 1 0 1 1 3
样例输出 Sample Output
4
