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