题意描述：
马从棋盘上的(1, 1)点出发（棋盘大小为p*q），问存不存在一条路，使得马能够遍历一遍棋盘上所有的点仅且一次。如果存在，输出遍历时所走的路径；如果有多条，输出字典序最小的那一条。
解题思路：
回溯法的应用，每一点马最多能往8个方向走。找到存在的路并不难，问题是如何找到字典序最小的那一条。如果想明白的话，这一个输出条件的限制也是很好满足的，
只与要在走下一步的时候，优先考虑序号较小的那一个即可。这样，找到的第一条路，一定是满足题意的。这一点我没有想到，再次感谢冰冰学长~~
简单说一下回溯法，回溯跟深度优先遍历是分不开的，我们倾向于把回溯看做深度优先遍历的延伸。我们知道，图的深度优先遍历每个节点只会被访问一次，因为我们一旦走过一个点，我们就会做相应的标记，避免重复经过同一个点。而回溯的做法是，当走过某一个点时，标记走过，并把该点压栈；当该节点出栈时，我们再把它标记为没有走过，这样就能保证另外一条路也能经过该点了。应用回溯法时，一定要注意剪枝，剪枝的好坏对程序的效率有很明显的影响。
图的深度优先遍历请参阅：
http://www.cppblog.com/hoolee/archive/2012/08/20/187754.html以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 40
#define LEN1 1000
typedef struct
{
int x;
int y;
}Point;
Point stk[LEN1];
int tp;
int mp[LEN][LEN];
int p, q;
int count;
int find;
int d[8][2] = {-1, -2, 1, -2, -2, -1, 2, -1, -2, 1, 2, 1, -1, 2, 1, 2};
int canWalk(int a, int b)
{
if(a >= 0 && a < p && b >= 0 && b < q && mp[a][b] == 0)
return 1;
return 0;
}
void DFS(int x0, int y0)
{
int i, j;
if(find == 1)
return;
if(tp < p * q)
{
for(i = 0; i < 8; i++)
{
int x1 = x0 + d[i][0];
int y1 = y0 + d[i][1];
if(canWalk(x1, y1))
{
mp[x1][y1] = 1;
stk[tp].x = x1;
stk[tp++].y = y1;
DFS(x1, y1);
mp[x1][y1] = 0;
tp--;
}
}
}
else
{
find = 1;
printf("Scenario #%d:\n", count++);
for(i = 0; i < tp; i++)
printf("%c%d", stk[i].y + 'A',stk[i].x + 1);
printf("\n\n");
}
}
int main()
{
int i, j;
int T;
scanf("%d", &T);
count = 1;
for(i = 1; i <= T; i++)
{
scanf("%d%d", &p, &q);
memset(mp, 0, sizeof(mp));
find = 0;
mp[0][0] = 1;
stk[0].x = stk[0].y = 0;
tp = 1;
DFS(0, 0);
if(find == 0)
{
printf("Scenario #%d:\n", count++);
printf("impossible\n\n");
}
}
//system("pause");
}
posted on 2012-08-20 16:09
小鼠标 阅读(433)
评论(0) 编辑 收藏 引用 所属分类:
图论