題意描述：
馬從棋盤上的(1, 1)點出發(fā)（棋盤大小為p*q），問存不存在一條路，使得馬能夠遍歷一遍棋盤上所有的點僅且一次。如果存在，輸出遍歷時所走的路徑；如果有多條，輸出字典序最小的那一條。
解題思路：
回溯法的應用，每一點馬最多能往8個方向走。找到存在的路并不難，問題是如何找到字典序最小的那一條。如果想明白的話，這一個輸出條件的限制也是很好滿足的，
只與要在走下一步的時候，優(yōu)先考慮序號較小的那一個即可。這樣，找到的第一條路，一定是滿足題意的。這一點我沒有想到，再次感謝冰冰學長~~
簡單說一下回溯法，回溯跟深度優(yōu)先遍歷是分不開的，我們傾向于把回溯看做深度優(yōu)先遍歷的延伸。我們知道，圖的深度優(yōu)先遍歷每個節(jié)點只會被訪問一次，因為我們一旦走過一個點，我們就會做相應的標記，避免重復經(jīng)過同一個點。而回溯的做法是，當走過某一個點時，標記走過，并把該點壓棧；當該節(jié)點出棧時，我們再把它標記為沒有走過，這樣就能保證另外一條路也能經(jīng)過該點了。應用回溯法時，一定要注意剪枝，剪枝的好壞對程序的效率有很明顯的影響。
圖的深度優(yōu)先遍歷請參閱：
http://www.shnenglu.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
小鼠標 閱讀(475)
評論(0) 編輯 收藏 引用 所屬分類:
圖論