POJ2248 A Knight's Journey(DFS)

题目链接

题目大意:

给定一个矩阵,马的初始位置在(0,0),要求给出一个方案,使马走遍所有的点。

列为数字,行为字母,搜索按字典序。

分析:

用 vis[x][y] 标记是否已经访问。因为要搜索所有的可能,所以没搜索完一次要把vis[x][y]标记为未访问。详情见代码。

用 p[x][y] 表示 (x,y)点的祖先,以便输出路径。

dfs搜索即可。

#include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <cstring> using namespace std; const int maxn = ;
const int VAL = ; int dx[] = {-, , -, , -, , -, }; //搜索顺序是字典序
int dy[] = {-, -, -, -, , , , }; bool vis[maxn][maxn];
int p[maxn][maxn], ex, ey;
int cnt, total, n, m; bool dfs(int x, int y, int px, int py) {
p[x][y] = px*VAL+py; cnt++; //如果已经走遍的点等于总点数,表示已经全部访问完
if(cnt == total) {
ex = x; ey = y;
return true;
} for(int d=; d<; d++) {
int nx = x+dx[d];
int ny = y+dy[d]; if(nx < || ny < || nx >= n || ny >= m) continue;
if(vis[nx][ny]) continue; vis[nx][ny] = true; //标记已访问 if(dfs(nx, ny, x, y)) return true; vis[nx][ny] = false; //标记未访问
cnt--; //已访问的数要减一
} return false;
} void print(int x, int y) {
if(x == && y == ) return;
int e = p[x][y];
int px = e/VAL, py = e%VAL;
print(px, py);
printf("%c%d", y+'A', x+); //y对应字母,x对应数字
} int main(){
int T;
scanf("%d", &T);
for(int kase=; kase<=T; kase++) {
scanf("%d%d", &n, &m);
cnt = ; total = n*m; memset(vis, , sizeof(vis)); vis[][] = true; printf("Scenario #%d:\n", kase); if(dfs(, , , )) { //有方案,输出
printf("A1");
print(ex, ey);
putchar('\n');
}
else printf("impossible\n");
putchar('\n');
} return ;
}
上一篇:Python练手例子(2)


下一篇:关于MySQL中的left join、on、where的一点深入