{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"福尔摩张发现自己在一个迷宫里,迷宫有一个出口。对于本来就是路痴的福尔摩张而言出去就已经很不容易了。并且身上还带着一枚定时炸弹。福尔摩张必须在炸弹爆炸前离开迷宫。上帝还算有点良心,将炸弹的初始爆炸时间设定为6分钟。对于天生腿长的福尔摩张,可以从一个区域移动到最近的区域(也就是说,如果福尔摩张现在站在(x,y)上,他只能在(x+1,y)、(x-1,y)、(x,y+1)或(x,y-1)下一分钟)上花费1分钟。迷宫里有时光机,可以将爆炸时间重置为6分钟。\n给定迷宫的布局和福尔摩张的起始位置,请告诉福尔摩张他是否能走出迷宫,如果他能,输出他找到迷宫出口所需要的最小时间,否则输出-1。\n以下是一些规则:\n1. 每分钟,福尔摩张只能走到最近的一个地方,他不能走出边界,当然他也不能在墙上走。\n2.如果福尔摩张在爆炸时间变为0时到达出口或者到达有时光机的地方,他还是死了。\n3. 只要你愿意,一个地方的时光机可以被使用很多次,如果有十分的把握出去,福尔摩张还可以参观迷宫。\n4. 重置爆炸时间的时间可以忽略,换句话说,如果福尔摩张到达一个包含时光机的区域,爆炸时间大于0,爆炸时间将重置为6。"}},{"title":"Input","value":{"format":"HTML","content":"输入包含几个测试用例。输入的第一行是单个整数T,它是测试用例的数量。T测试用例如下。\n\u003cbr\u003e每个测试用例开始时都有两个整数N和M(1\u0026lt;\u003dN,Mm\u003d8),表示迷宫的大小。然后是N行,每一行包含M个整数。阵列表示迷宫的布局。\n\u003cbr\u003e有5个整数表示迷宫中不同类型的面积:\n0表示这个区域是一堵墙,福尔摩张不应该在上面走。\n1表示这个区域什么都没有,福尔摩张可以在上面行走。\n\u003cbr\u003e2表示平平的起始位置,福尔摩张从这个位置开始逃脱。\n\u003cbr\u003e3表示迷宫的出口,福尔摩张的目标位置。\n4:该地区有一个时光机,福尔摩张可以通过步行到这些地区来延迟爆炸时间。\n\u003c br \u003e"}},{"title":"Output","value":{"format":"HTML","content":"对于每个测试用例,如果福尔摩张能够走出迷宫,您应该输出他需要的最小时间,否则您应该输出-1。\n\u003c br \u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e3\n3 3\n2 1 1\n1 1 0\n1 1 3\n4 8\n2 1 1 0 1 1 1 0\n1 0 4 1 1 0 4 1\n1 0 0 0 0 0 0 1\n1 1 1 4 1 1 1 3\n5 8\n1 2 1 1 1 1 1 4 \n1 0 0 0 1 0 0 1 \n1 4 1 0 1 1 0 1 \n1 0 0 0 0 3 0 1 \n1 1 4 1 1 1 1 1 \u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e4\n-1\n13\u003c/pre\u003e"}}]}