深度优先搜索加回溯。之前用四叉树的记录遍历迷宫的所有路径，结果内存超限制了，请教学长之后才知道有种算法设计方法叫“回溯”，即在沿一条路深度遍历后再把走过的路标记回来，这样就能避免影响其它路径的遍历。
另外关于递归要说一点，当递归中涉及到对全局变量（比如一个全局的数组）的修改时，之前我一直存在的疑问是：如果递归式树状调用结构，那么每一时刻这个全局的数组在被谁使用呢？如果每层递归都能同时使用该数组，那数据不就乱了吗？原来虽然递归的调用可以是树状的，但是每一个时刻递归都是沿着递归树中的一条路在走，一条路走不通了才会退一步，换个子树接着走。这些都是在了解回溯之后才想通的。
#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
小鼠标 阅读(195)
评论(0) 编辑 收藏 引用