{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003e今年的奥运会之后,在行星mm-21上冰壶越来越受欢迎。但是规则和我们的有点不同。这个游戏是在一个冰游戏板上玩的,上面有一个正方形网格。他们只用一块石头。游戏的目的是让石子从起点到终点,并且移动的次数最小\u003c/p\u003e\n \u003cp\u003e图1显示了一个游戏板的例子。一些正方形格子可能被砖块占据。有两个特殊的格子,起始点和目标点,这是不占用块。一旦石头开始移动就不会停下,除非它击中砖块或飞出边界。\u003c/p\u003e\n \u003cp align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/dfcadffc211686655c382e9ad94bdbfe?v\u003d1485266318\" SRC\u003d\"CDN_BASE_URL/dfcadffc211686655c382e9ad94bdbfe?v\u003d1485266318\"\u003e\u003cbr\u003e图1:例子(S:开始,G:目标)\u003c/p\u003e\n \u003cp\u003e石头的运动遵循以下规则:\u003c/p\u003e\n \u003cul\u003e\n \u003cli\u003e开始时,石头静止起点广场上。\u003c/li\u003e\n \u003cli\u003e石头的运动仅限于x和y方向。禁止对角线移动。\u003c/li\u003e\n \u003cli\u003e当石头静止时,你可以让他向任意方向移动,除非它移动的方向上有砖块(图2(a))。\u003c/li\u003e\n \u003cli\u003e一旦抛出,石头不断向同一方向移动,直到下列事件之一发生:\n \u003cul\u003e\n \u003cli\u003e石头击中砖块(图2(b),(c))。. \n \u003cul\u003e\n \u003cli\u003e石头停在他击中的砖块之前 \u003c/li\u003e\n \u003cli\u003e被击中的砖块消失\u003c/li\u003e\n \u003c/ul\u003e\u003c/li\u003e\n \u003cli\u003e石块飞出游戏板之外。\n \u003cul\u003e\n \u003cli\u003e游戏结束的条件 \u003c/li\u003e\n \u003c/ul\u003e\u003c/li\u003e\n \u003cli\u003e到达目标点(经过终点就算抵达)\n \u003cul\u003e\n \u003cli\u003e石头经过目标点游戏成功 \u003c/li\u003e\n \u003c/ul\u003e\u003c/li\u003e\n \u003c/ul\u003e\u003c/li\u003e\n \u003cli\u003e不能在十步之内到达目标点则返回失败。\u003c/li\u003e\n \u003c/ul\u003e\n \u003cp align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/725189cee19b86e1cd2410490b0dadc2?v\u003d1485266318\" SRC\u003d\"CDN_BASE_URL/725189cee19b86e1cd2410490b0dadc2?v\u003d1485266318\"\u003e\u003cbr\u003eFig. 2: Stone movements\u003c/p\u003e\n \u003cp\u003e通过这些规则我们想知道,石头是否能够到达目标点和最少移动次数\u003c/p\u003e\n \u003cp\u003e初始配置如图1所示,石头从开始到目标需要4次移动。路线如图3所示(a)。注意当石头到达目标时,游戏版的配置如图3(b)改变。\u003c/p\u003e\n \u003cp align\u003d\"center\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/c657651fda754a877e0c3a2ce3a06fd7?v\u003d1485266318\" SRC\u003d\"CDN_BASE_URL/c657651fda754a877e0c3a2ce3a06fd7?v\u003d1485266318\"\u003e\u003cbr\u003e图3:图1的解决方案和解决之后的结果。\u003c/p\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003e输入是一组数据。输入结束标志为两个0。数据组的数量不超过100。\u003c/p\u003e\n \u003cp\u003e每个数据集如下展示\u003c/p\u003e\n \u003cblockquote\u003e\n \u003cp\u003e\u003ci\u003e板的宽度(w)和高度(h)\u003c/i\u003e \u003cbr\u003e\u003ci\u003e游戏版的第一行\u003c/i\u003e \u003cbr\u003e... \u003cbr\u003e\u003ci\u003e游戏版的h-th行 \u003c/i\u003e\u003c/p\u003e\n \u003c/blockquote\u003e\n \u003cp\u003e版的宽和高满足: 2 \u0026lt;\u003d \u003ci\u003ew\u003c/i\u003e \u0026lt;\u003d 20, 1 \u0026lt;\u003d \u003ci\u003eh\u003c/i\u003e \u0026lt;\u003d 20.\u003c/p\u003e\n \u003cp\u003e每行由一个空格分隔的十进制数字组成。该数字描述相应的格子的状态。\u003c/p\u003e\n \u003cblockquote\u003e\n \u003ctable id\u003d\"table1\"\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e0 \u003c/td\u003e\n \u003ctd\u003e空\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003e1 \u003c/td\u003e\n \u003ctd\u003e砖块\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003e2 \u003c/td\u003e\n \u003ctd\u003e开始点\u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd\u003e3 \u003c/td\u003e\n \u003ctd\u003e目标点\u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\n \u003c/table\u003e\n \u003c/blockquote\u003e\n \u003cp\u003e 图. D-1数据如下:\u003c/p\u003e\n \u003cblockquote\u003e\n \u003cp\u003e6 6 \u003cbr\u003e1 0 0 2 1 0 \u003cbr\u003e1 1 0 0 0 0 \u003cbr\u003e0 0 0 0 0 3 \u003cbr\u003e0 0 0 0 0 0 \u003cbr\u003e1 0 0 0 0 1 \u003cbr\u003e0 1 1 1 1 1\u003c/p\u003e\n \u003c/blockquote\u003e\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n \u003cp\u003e对于每个数据,打印一个十进制整数的行,表示从开始到目标的路径的最小移动次数。如果没有这样的路线,打印- 1。每个行不应该有这个数字以外的任何字符。\u003c/p\u003e\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e2 1\n3 2\n6 6\n1 0 0 2 1 0\n1 1 0 0 0 0\n0 0 0 0 0 3\n0 0 0 0 0 0\n1 0 0 0 0 1\n0 1 1 1 1 1\n6 1\n1 1 2 1 1 3\n6 1\n1 0 2 1 1 3\n12 1\n2 0 1 1 1 1 1 1 1 1 1 3\n13 1\n2 0 1 1 1 1 1 1 1 1 1 1 3\n0 0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e1\n4\n-1\n4\n10\n-1\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":""}},{"title":"","value":{"format":"HTML","content":""}}]}