{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\r\n #problem-ul-reset{\r\n list-style-position: inside;\r\n list-style-type: decimal;\r\n margin: 15px;\r\n }\r\n #problem-ul-reset li { margin:5px 0; }\r\n #prog-content img { width: 35%; }\r\n\u003c/style\u003e \n \u003cdiv id\u003d\"prog-content\"\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Hi:小Ho你会下国际象棋么?\u003c/p\u003e \n \u003cp\u003e小Ho:应该算会吧,我知道每个棋子的移动方式,马走日象飞田什么的...\u003c/p\u003e \n \u003cp\u003e小Hi:象飞田那是中国象棋啦!\u003c/p\u003e \n \u003cp\u003e小Ho:哦,对。国际象棋好像是走斜线来着。\u003c/p\u003e \n \u003cp\u003e小Hi:不过马走日倒是对了。国际象棋中的马一般叫做骑士,关于它有个很有意思的问题。\u003c/p\u003e \n \u003cp\u003e小Ho:什么啊?\u003c/p\u003e \n \u003cp\u003e小Hi:骑士巡游问题,简单来说就是关于在棋盘上放置若干个骑士,然后探究移动这些骑士是否能满足一定的而要求。举个例子啊:一个骑士从起始点开始,能否经过棋盘上所有的格子再回到起点。\u003c/p\u003e \n \u003cp\u003e小Ho:哦,看上去好像很难的样子。\u003c/p\u003e \n \u003cp\u003e小Hi:其实也还好了。简单一点的比如棋盘上有3个骑士,能否通过若干次移动走到一起。\u003c/p\u003e \n \u003cp\u003e小Ho:能够么?\u003c/p\u003e \n \u003cp\u003e小Hi:当然能够了。由于骑士特殊的移动方式,放置在任何一个初始位置的骑士,都可以通过若干次移动到达棋盘上任意一个位置。\u003c/p\u003e \n \u003cp\u003e小Ho:那么只要选定一个位置,把它们全部移动过去就好了是吧?\u003c/p\u003e \n \u003cp\u003e小Hi:是的,那么这里又有另一个问题了:要选择哪一个位置汇合,使得3个骑士行动的总次数最少?\u003c/p\u003e \n \u003cp\u003e小Ho:嗯,这个好像不是很难,让我想一想。\u003c/p\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示:骑士问题\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\" style\u003d\"width: 870px;\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:骑士问题\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Ho:小Hi你刚刚说到了这样一点:\u003cb\u003e放置在任何一个初始位置的骑士,都可以通过若干次移动到达棋盘上任意一个位置。\u003c/b\u003e\u003c/p\u003e \n \u003cp\u003e那么我就可以把整个局面分开来做:我先计算出每一个骑士到达棋盘上每个位置的最短距离;再枚举每一个位置,表示将三个骑士在这个位置上汇合,累加这三个骑士到达的步数之和;最后选择一个最小的和作为解。\u003c/p\u003e \n \u003cp\u003e求解骑士到达每一个位置最少步数时,我可以使用之前讲过的\u003cb\u003e宽度优先搜索\u003c/b\u003e。从而保证我第一次枚举到这个位置时就是最少的步数。\u003c/p\u003e \n \u003cp\u003e那么整个流程就是:\u003c/p\u003e \n \u003cpre\u003ebfs_solve(f, x, y):\r\n\tf[][] \u003d -1\t// 初始化为-1\r\n\tf[x][y] \u003d 0\t// 起始点\r\n\tqueue.push( (x,y) ) // 将初始点加入队列中\r\n\twhile (!queue.isEmpty())\r\n\t\t(now_x, now_y) \u003d queue.pop()\t// 弹出队列头元素\r\n\t\tFor i \u003d 1 .. 8\r\n\t\t\t// 枚举8种可能的移动\r\n\t\t\t(next_x, next_y) \u003d move(now_x, now_y, i)\r\n\t\t\tIf ((next_x, next_y) in chessboard AND f[next_x][next_y] equal -1)\r\n\t\t\t\tf[next_x][next_y] \u003d f[now_x][now_y] + 1\r\n\t\t\t\tqueue.push( (next_x, next_y) )\r\n\t\t\tEnd If\r\n\t\tEnd For\r\n\tEnd While\r\n\r\nFor i \u003d 1 .. 3\r\n\t// 通过bfs求解\r\n\t// step[i][x][y]表示第i个骑士移动到(x,y)的最少步数\r\n\tbfs_solve(step[i][][], initialX[i], initialY[i])\r\nEnd \r\nans \u003d Infinite\r\nFor x \u003d A .. H\r\n\tFor y \u003d 1 .. 8\r\n\t\tIf (ans \u0026gt; sigma(step[][x][y])) Then\r\n\t\t\tans \u003d sigma(step[][x][y])\r\n\t\tEnd If\r\n\tEnd For\r\nEnd For\u003c/pre\u003e \n \u003cp\u003e小Hi:小Ho挺厉害的嘛,这样的确把问题解决了。不过我这里还有另一种方法,虽然同样是通过宽度优先搜索来搜索最少步数,但是我将三个骑士的位置看做了一个整体。\u003c/p\u003e \n \u003cp\u003e由于每一个骑士的位置都是由2个坐标来决定,这俩个坐标恰好可以对应一个2位的八进制数。若我把3个坐标合起来,就可以用一个6位的八进制数来表示。比如\"B2 D3 F4\",就表示为\"113253\"。\u003c/p\u003e \n \u003cp\u003e由此可以通过一个大小为8^6的布尔数组来进行状态的判重。而每一次的状态转移也从原来的仅枚举8个方向,变成了枚举骑士加枚举方向,一共有3*8\u003d24种可能。\u003c/p\u003e \n \u003cp\u003e此方法的伪代码为:\u003c/p\u003e \n \u003cpre\u003equeue.push( initialStatus ) // 将初始的8进制数加入队列中\r\nwhile (!queue.isEmpty())\r\n\tnow_status \u003d queue.pop()\t// 弹出队列头元素\r\n\tFor i \u003d 1 .. 3\r\n\t// 枚举移动的其实\r\n\t\tFor j \u003d 1 .. 8\r\n\t\t// 枚举8种可能的移动\r\n\t\tnext_status \u003d move(now_status, i, j)\t// 移动骑士并记录状态\t\r\n\t\tIf (next_status is valid AND not visited[ next_status ])\r\n\t\t\tstep[ next_status ] \u003d step[ now_status ] + 1\r\n\t\t\tqueue.push( next_status )\r\n\t\t\tIf (check(next_status)) Then\r\n\t\t\t\t// 检查这个八进制数是否满足3个坐标重合\r\n\t\t\t\tReturn step[ next_status ]\r\n\t\t\tEnd If \r\n\t\tEnd If\r\n\tEnd For\r\nEnd While\u003c/pre\u003e \n \u003cp\u003e在进行检查是否已经走到一起时,可以通过一个位运算来做:\u003c/p\u003e \n \u003cpre\u003echeck(status):\r\n\tReturn ((status and 0x3f) \u003d\u003d ((status rsh 6) and 0x3f)) and (((status rsh 6) and 0x3f) \u003d\u003d ((status rsh 12) and 0x3f))\r\n\t// rsh表示右移操作\u003c/pre\u003e \n \u003cp\u003e小Ho:哦,这样就可以不用计算出每个骑士走到每个点的步数,而是在过程中就有可能直接求解到最先汇合位置的步数。\u003c/p\u003e \n \u003cp\u003e小Hi:对,不过这个算法中状态的转移会稍微复杂一点。你可以选择一个你比较喜欢的方法来实现。\u003c/p\u003e \n \u003cp\u003e小Ho:好!\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第1行:1个正整数t,表示数据组数,2≤t≤10。\u003c/p\u003e \n \u003cp\u003e第2..t+1行:用空格隔开的3个坐标, 每个坐标由2个字符AB组成,A为\u0027A\u0027~\u0027H\u0027的大写字母,B为\u00271\u0027~\u00278\u0027的数字,表示3个棋子的初始位置。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e第1..t行:每行1个数字,第i行表示第i组数据中3个棋子移动到同一格的最小行动步数。\u003c/p\u003e \n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e2\r\nA1 A1 A1\r\nB2 D3 F4\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e0\r\n2\u003c/pre\u003e \n\u003c/dd\u003e\n\u003cdiv\u003e \n \u003cstyle type\u003d\"text/css\"\u003e\r\n #problem-ul-reset{\r\n list-style-position: inside;\r\n list-style-type: decimal;\r\n margin: 15px;\r\n }\r\n #problem-ul-reset li { margin:5px 0; }\r\n #prog-content img { width: 35%; }\r\n\u003c/style\u003e \n \u003cdiv id\u003d\"prog-content\"\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e描述\u003c/h4\u003e \n \u003cp\u003e小Hi:小Ho你会下国际象棋么?\u003c/p\u003e \n \u003cp\u003e小Ho:应该算会吧,我知道每个棋子的移动方式,马走日象飞田什么的...\u003c/p\u003e \n \u003cp\u003e小Hi:象飞田那是中国象棋啦!\u003c/p\u003e \n \u003cp\u003e小Ho:哦,对。国际象棋好像是走斜线来着。\u003c/p\u003e \n \u003cp\u003e小Hi:不过马走日倒是对了。国际象棋中的马一般叫做骑士,关于它有个很有意思的问题。\u003c/p\u003e \n \u003cp\u003e小Ho:什么啊?\u003c/p\u003e \n \u003cp\u003e小Hi:骑士巡游问题,简单来说就是关于在棋盘上放置若干个骑士,然后探究移动这些骑士是否能满足一定的而要求。举个例子啊:一个骑士从起始点开始,能否经过棋盘上所有的格子再回到起点。\u003c/p\u003e \n \u003cp\u003e小Ho:哦,看上去好像很难的样子。\u003c/p\u003e \n \u003cp\u003e小Hi:其实也还好了。简单一点的比如棋盘上有3个骑士,能否通过若干次移动走到一起。\u003c/p\u003e \n \u003cp\u003e小Ho:能够么?\u003c/p\u003e \n \u003cp\u003e小Hi:当然能够了。由于骑士特殊的移动方式,放置在任何一个初始位置的骑士,都可以通过若干次移动到达棋盘上任意一个位置。\u003c/p\u003e \n \u003cp\u003e小Ho:那么只要选定一个位置,把它们全部移动过去就好了是吧?\u003c/p\u003e \n \u003cp\u003e小Hi:是的,那么这里又有另一个问题了:要选择哪一个位置汇合,使得3个骑士行动的总次数最少?\u003c/p\u003e \n \u003cp\u003e小Ho:嗯,这个好像不是很难,让我想一想。\u003c/p\u003e \n \u003cp\u003e\u003ca href\u003d\"#\" data-toggle\u003d\"modal\" data-target\u003d\"#m2\"\u003e提示:骑士问题\u003c/a\u003e\u003c/p\u003e \u003c!-- Modal --\u003e \n \u003cdiv class\u003d\"modal\" id\u003d\"m2\" tabindex\u003d\"-1\" role\u003d\"dialog\" aria-labelledby\u003d\"myModalLabel\" aria-hidden\u003d\"true\"\u003e \n \u003cdiv class\u003d\"modal-dialog\" style\u003d\"width: 870px;\"\u003e \n \u003cdiv class\u003d\"modal-content\"\u003e \n \u003cdiv class\u003d\"modal-header\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"close\" data-dismiss\u003d\"modal\" aria-label\u003d\"Close\"\u003e\u003cspan aria-hidden\u003d\"true\"\u003e×\u003c/span\u003e\u003c/button\u003e \n \u003ch4 class\u003d\"modal-title\" id\u003d\"myModalLabel\"\u003e提示:骑士问题\u003c/h4\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-body\"\u003e \n \u003cp\u003e小Ho:小Hi你刚刚说到了这样一点:\u003cb\u003e放置在任何一个初始位置的骑士,都可以通过若干次移动到达棋盘上任意一个位置。\u003c/b\u003e\u003c/p\u003e \n \u003cp\u003e那么我就可以把整个局面分开来做:我先计算出每一个骑士到达棋盘上每个位置的最短距离;再枚举每一个位置,表示将三个骑士在这个位置上汇合,累加这三个骑士到达的步数之和;最后选择一个最小的和作为解。\u003c/p\u003e \n \u003cp\u003e求解骑士到达每一个位置最少步数时,我可以使用之前讲过的\u003cb\u003e宽度优先搜索\u003c/b\u003e。从而保证我第一次枚举到这个位置时就是最少的步数。\u003c/p\u003e \n \u003cp\u003e那么整个流程就是:\u003c/p\u003e \n \u003cpre\u003ebfs_solve(f, x, y):\r\n\tf[][] \u003d -1\t// 初始化为-1\r\n\tf[x][y] \u003d 0\t// 起始点\r\n\tqueue.push( (x,y) ) // 将初始点加入队列中\r\n\twhile (!queue.isEmpty())\r\n\t\t(now_x, now_y) \u003d queue.pop()\t// 弹出队列头元素\r\n\t\tFor i \u003d 1 .. 8\r\n\t\t\t// 枚举8种可能的移动\r\n\t\t\t(next_x, next_y) \u003d move(now_x, now_y, i)\r\n\t\t\tIf ((next_x, next_y) in chessboard AND f[next_x][next_y] equal -1)\r\n\t\t\t\tf[next_x][next_y] \u003d f[now_x][now_y] + 1\r\n\t\t\t\tqueue.push( (next_x, next_y) )\r\n\t\t\tEnd If\r\n\t\tEnd For\r\n\tEnd While\r\n\r\nFor i \u003d 1 .. 3\r\n\t// 通过bfs求解\r\n\t// step[i][x][y]表示第i个骑士移动到(x,y)的最少步数\r\n\tbfs_solve(step[i][][], initialX[i], initialY[i])\r\nEnd \r\nans \u003d Infinite\r\nFor x \u003d A .. H\r\n\tFor y \u003d 1 .. 8\r\n\t\tIf (ans \u0026gt; sigma(step[][x][y])) Then\r\n\t\t\tans \u003d sigma(step[][x][y])\r\n\t\tEnd If\r\n\tEnd For\r\nEnd For\u003c/pre\u003e \n \u003cp\u003e小Hi:小Ho挺厉害的嘛,这样的确把问题解决了。不过我这里还有另一种方法,虽然同样是通过宽度优先搜索来搜索最少步数,但是我将三个骑士的位置看做了一个整体。\u003c/p\u003e \n \u003cp\u003e由于每一个骑士的位置都是由2个坐标来决定,这俩个坐标恰好可以对应一个2位的八进制数。若我把3个坐标合起来,就可以用一个6位的八进制数来表示。比如\"B2 D3 F4\",就表示为\"113253\"。\u003c/p\u003e \n \u003cp\u003e由此可以通过一个大小为8^6的布尔数组来进行状态的判重。而每一次的状态转移也从原来的仅枚举8个方向,变成了枚举骑士加枚举方向,一共有3*8\u003d24种可能。\u003c/p\u003e \n \u003cp\u003e此方法的伪代码为:\u003c/p\u003e \n \u003cpre\u003equeue.push( initialStatus ) // 将初始的8进制数加入队列中\r\nwhile (!queue.isEmpty())\r\n\tnow_status \u003d queue.pop()\t// 弹出队列头元素\r\n\tFor i \u003d 1 .. 3\r\n\t// 枚举移动的其实\r\n\t\tFor j \u003d 1 .. 8\r\n\t\t// 枚举8种可能的移动\r\n\t\tnext_status \u003d move(now_status, i, j)\t// 移动骑士并记录状态\t\r\n\t\tIf (next_status is valid AND not visited[ next_status ])\r\n\t\t\tstep[ next_status ] \u003d step[ now_status ] + 1\r\n\t\t\tqueue.push( next_status )\r\n\t\t\tIf (check(next_status)) Then\r\n\t\t\t\t// 检查这个八进制数是否满足3个坐标重合\r\n\t\t\t\tReturn step[ next_status ]\r\n\t\t\tEnd If \r\n\t\tEnd If\r\n\tEnd For\r\nEnd While\u003c/pre\u003e \n \u003cp\u003e在进行检查是否已经走到一起时,可以通过一个位运算来做:\u003c/p\u003e \n \u003cpre\u003echeck(status):\r\n\tReturn ((status and 0x3f) \u003d\u003d ((status rsh 6) and 0x3f)) and (((status rsh 6) and 0x3f) \u003d\u003d ((status rsh 12) and 0x3f))\r\n\t// rsh表示右移操作\u003c/pre\u003e \n \u003cp\u003e小Ho:哦,这样就可以不用计算出每个骑士走到每个点的步数,而是在过程中就有可能直接求解到最先汇合位置的步数。\u003c/p\u003e \n \u003cp\u003e小Hi:对,不过这个算法中状态的转移会稍微复杂一点。你可以选择一个你比较喜欢的方法来实现。\u003c/p\u003e \n \u003cp\u003e小Ho:好!\u003c/p\u003e \n \u003c/div\u003e \n \u003cdiv class\u003d\"modal-footer\"\u003e \u003cbutton type\u003d\"button\" class\u003d\"btn btn-default\" data-dismiss\u003d\"modal\"\u003eClose\u003c/button\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003c/div\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输入\u003c/h4\u003e \n \u003cp\u003e第1行:1个正整数t,表示数据组数,2≤t≤10。\u003c/p\u003e \n \u003cp\u003e第2..t+1行:用空格隔开的3个坐标, 每个坐标由2个字符AB组成,A为\u0027A\u0027~\u0027H\u0027的大写字母,B为\u00271\u0027~\u00278\u0027的数字,表示3个棋子的初始位置。\u003c/p\u003e \n \u003ch4 style\u003d\"font-weight:bold;\"\u003e输出\u003c/h4\u003e \n \u003cp\u003e第1..t行:每行1个数字,第i行表示第i组数据中3个棋子移动到同一格的最小行动步数。\u003c/p\u003e \n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdt\u003e\n Sample Input \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e2\r\nA1 A1 A1\r\nB2 D3 F4\u003c/pre\u003e \n\u003c/dd\u003e \n\u003cdt\u003e\n Sample Output \n\u003c/dt\u003e \n\u003cdd\u003e \n \u003cpre\u003e0\r\n2\u003c/pre\u003e \n\u003c/dd\u003e"}}]}