深度優(yōu)先搜索加回溯。之前用四叉樹的記錄遍歷迷宮的所有路徑，結(jié)果內(nèi)存超限制了，請教學(xué)長之后才知道有種算法設(shè)計方法叫“回溯”，即在沿一條路深度遍歷后再把走過的路標(biāo)記回來，這樣就能避免影響其它路徑的遍歷。
另外關(guān)于遞歸要說一點，當(dāng)遞歸中涉及到對全局變量（比如一個全局的數(shù)組）的修改時，之前我一直存在的疑問是：如果遞歸式樹狀調(diào)用結(jié)構(gòu)，那么每一時刻這個全局的數(shù)組在被誰使用呢？如果每層遞歸都能同時使用該數(shù)組，那數(shù)據(jù)不就亂了嗎？原來雖然遞歸的調(diào)用可以是樹狀的，但是每一個時刻遞歸都是沿著遞歸樹中的一條路在走，一條路走不通了才會退一步，換個子樹接著走。這些都是在了解回溯之后才想通的。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
char x;
char y;
}Node;
int fd;//have find given length
int T;
int len;
char mp[8][8];//map
void f(int x, int y)
{
if(!fd)
{
if(mp[x - 1][y] == 'D' && len + 1 == T)fd = 1;
else if(mp[x - 1][y] == '.')//go up
{
len ++;
mp[x - 1][y] = 'X';
f(x - 1, y);
len --;
mp[x - 1][y] = '.';
}
if(mp[x][y + 1] == 'D' && len + 1 == T)fd = 1;
else if(mp[x][y + 1] == '.')//go right
{
len ++;
mp[x][y + 1] = 'X';
f(x, y + 1);
len --;
mp[x][y + 1] = '.';
}
if(mp[x + 1][y] == 'D' && len + 1 == T)fd = 1;
else if(mp[x + 1][y] == '.')//go down
{
len ++;
mp[x + 1][y] = 'X';
f(x + 1, y);
len --;
mp[x + 1][y] = '.';
}
if(mp[x][y - 1] == 'D' && len + 1 == T)fd = 1;
else if(mp[x][y - 1] == '.')//go left
{
len ++;
mp[x][y - 1] = 'X';
f(x, y - 1);
len --;
mp[x][y - 1] = '.';
}
}
}
int main()
{
int N, M;
int i, j;
int find;
Node s;
scanf("%d%d%d", & N, & M, & T);
while(N + M + T != 0)
{
for(i = 1; i <= N; i++)//read map
scanf("%s",&mp[i][1]);
for(i = 1; i <= N; i++)
for(j = 1; j <= M; j++)
if(mp[i][j] == 'X')
for(i = 0; i <= N + 1; i++)//init map
mp[i][0] = mp[i][M + 1] = 'X';
for(i = 1; i <= M; i++)
mp[0][i] = mp[N + 1][i] = 'X';
find = 0;
for(i = 1; i <= N && find == 0; i++)//search start point
for(j = 1; j<= M && find == 0; j++)
if(mp[i][j] == 'S')
{
s.x = i;
s.y = j;
find = 1;
}
fd = 0;
len = 0;
f(s.x, s.y);
if(fd == 1)
puts("YES");
else
puts("NO");
scanf("%d%d%d", & N, & M, & T);
}
}
posted on 2012-02-28 17:14
小鼠標(biāo) 閱讀(224)
評論(0) 編輯 收藏 引用