2013-02-22 22:03:22Morris
[ZJ][bfs, dfs] a634. 14. Knights Path
內容 :
在西洋棋中,騎士的走法獨特而有趣。它只能沿著一個「L」形路徑走,先垂直或水平走兩格,然後向左或向右轉
90度後再走一格。右圖顯示一個標準的 8×8 棋盤,有一個騎士在 c6 這一格。從這個位置,士可以走到以圓圈標示的八個位。
你的工作是要找出騎士從棋盤上的一個位置走到另一個位置的最短路徑。與真正下棋時不同的是,你不可以落在有其他棋子的地方 (我們稱之為「路障」)。注意,騎士依上述方式移動每一步時,它可以「跨過」其他的棋子,但是必須茖在空的格子上。
輸入說明 :
每筆測資的第一行含有起始和結束的位置,以空白隔開。棋盤的左上角為 a8,右下角為 h1。所有的字母均為小寫。
接下來有一個或多個「路障」位置,最後一個路障之後會有一個「xx」作為結束。最多會有 31 個路障,所有的輸入都是正確的。
輸出說明 :
你的程式要輸出從起始位置到目的位罝的最短路徑中的每一步。你也要述明所需的總步數。如果有多條路徑,請依字典順序輸出所有的路徑。
範例輸入 :
c6 c5b3a6b7d7xx
範例輸出 :
The shortest solution is 3 move(s).Solution: c6 b4 d3 c5Solution: c6 d4 e6 c5Solution: c6 d8 e6 c5Solution: c6 e5 d3 c5
提示 :
//經查,本題原測資有誤,已更正并重測 by liouzhou_101 2013-02-22 14:15
出處 :
/**********************************************************************************/
/* Problem: a634 "14. Knights Path" from HP CodeWars 2007 */
/* Language: CPP (2188 Bytes) */
/* Result: AC(4ms, 452KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-02-20 16:41:25 */
/**********************************************************************************/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <set>
#include <queue>
using namespace std;
int g[8][8];
int dir[8][2] = {{1,2},{1,-2},{-1,2},{-1,-2},
{2,1},{2,-1},{-2,1},{-2,-1}};
set<string> sol;
int used[8][8], x, y, i, j;
char bufres[1024];
void dfs(int sx, int sy) {
if(used[sx][sy] == 1) {
sol.insert(bufres);
return;
}
int i, x, y, l = (used[sx][sy]-1)*3;
for(i = 0; i < 8; i++) {
x = sx+dir[i][0], y = sy+dir[i][1];
if(x < 0 || y < 0 || x >= 8 || y >= 8)
continue;
if(g[x][y])
continue;
if(used[x][y] == used[sx][sy]-1) {
bufres[l-1] = y+'1';
bufres[l-2] = x+'a';
bufres[l-3] = ' ';
dfs(x, y);
}
}
}
void bfs(int sx, int sy, int ex, int ey) {
queue<int> X, Y;
X.push(sx), Y.push(sy);
memset(used, 0, sizeof(used));
used[sx][sy] = 1;
while(!X.empty()) {
sx = X.front(), X.pop();
sy = Y.front(), Y.pop();
for(i = 0; i < 8; i++) {
x = sx+dir[i][0], y = sy+dir[i][1];
if(x < 0 || y < 0 || x >= 8 || y >= 8)
continue;
if(g[x][y] || used[x][y])
continue;
used[x][y] = used[sx][sy]+1;
X.push(x), Y.push(y);
}
}
printf("The shortest solution is %d move(s).\n", used[ex][ey]-1);
memset(bufres, 0, sizeof(bufres));
int l = used[ex][ey]*3;
bufres[l-1] = ey+'1';
bufres[l-2] = ex+'a';
bufres[l-3] = ' ';
dfs(ex, ey);
for(set<string>::iterator it = sol.begin();
it != sol.end(); it++) {
cout << "Solution:" << *it << endl;
}
sol.clear();
}
int main() {
char s[5];
int sx, sy, ex, ey, x, y;
while(scanf("%s", s) == 1) {
sx = s[0]-'a', sy = s[1]-'1';
scanf("%s", s);
ex = s[0]-'a', ey = s[1]-'1';
memset(g, 0, sizeof(g));
while(scanf("%s", s) == 1 && s[0] != 'x') {
x = s[0]-'a', y = s[1]-'1';
g[x][y] = -1;
}
bfs(sx, sy, ex, ey);
}
return 0;
}