【算法】深度优先搜索（DFS）III

1. DFS生成排列

众所周知，1,2…n的排列一共有n!个，因此生成全排列至少需要n!的时间复杂度。如果用循环来生成排列，当n稍大时，内外循环会非常之多。可以用DFS模拟解决，生成0 … n-1的排列的代码如下：

void dfs(int depth)
{
	int i,length;
	if(depth==n)                 //n个数排列完毕
	{
		print the result
		return;
	}

	for(i=0;i<n;i++)
		if(!visit[i])           //点i没被访问
		{
			visit[i]=1;
			result[depth]=i;
			dfs(depth+1);       //进入下一次递归
			visit[i]=0;         //回溯，将点i重新标记为未被访问
		}
}

2. 问题

2.1 POJ 2907

题目大意：从start点出发，经过n个beeper点后，回到start点；求最短路径。

思路：由于n<=10，可以用全排列解决。将n个beeper点排列，所得的序列即为经过beeper点的先后顺序，然后计算路径长度。在这n!个路径中，找出最小值。

源代码：

2907

Accepted

164K

0MS

1127B

2013-10-10 21:16:22

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "limits.h"

typedef struct position
{
	int x,y;
}Position;

int n,minimum,result[10],visit[10];
Position start,beeper[10];

int distance(Position a,Position b)
{
	return abs(a.x-b.x)+abs(a.y-b.y);
}

void dfs(int depth)
{
	int i,length;
	if(depth==n)
	{
		length=0;
		for(i=1;i<n;i++)
			length+=distance(beeper[result[i]],beeper[result[i-1]]);
		length+=distance(beeper[result[0]],start);
		length+=distance(beeper[result[n-1]],start);
		if(length<minimum)
			minimum=length;
		return;
	}

	for(i=0;i<n;i++)
		if(!visit[i])
		{
			visit[i]=1;
			result[depth]=i;
			dfs(depth+1);
			visit[i]=0;
		}
}

int main()
{
	int scenarios,xsize,ysize,i;
	scanf("%d",&scenarios);
	while(scenarios--)
	{
		scanf("%d%d",&xsize,&ysize);
		scanf("%d%d%d",&start.x,&start.y,&n);
		for(i=0;i<n;i++)
			scanf("%d%d",&beeper[i].x,&beeper[i].y);

		memset(visit,0,sizeof(visit));
		minimum=INT_MAX;
		dfs(0);
		printf("The shortest path has length %d
",minimum);

	}
	return 0;
}

2.2 POJ 1256

题目大意：有n个字母word，可能含有重复元素，求其全排列。

在DFS生成排列时，会碰到重复元素，为了不重复输出同一个排列，需要进行剪枝。扫描到当前字母i与其前一个字母i-1相同，且字母i-1未被访问，则选择跳过。

少写了一句结束标志 result[depth]=''; WA了N久。分析：因为result会记录上一个word的排列，所以会对下一个word产生影响；比如，输入abc和ab，等到输出ab的排列时，会输出cba的结果。

源代码：

1256

Accepted

156K

32MS

825B

2013-10-11 15:27:01

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "ctype.h"

int n,visit[13];
char word[13],result[13];

int cmp(const void *a,const void *b)
{
	char c=*(char *)a,d=*(char *)b;
	return tolower(c)==tolower(d)?c-d:tolower(c)-tolower(d);
}

void dfs(int depth)
{
	int i;
	if(depth==n)                 
	{
		result[depth]='';                        //少写了这一句，WA了N久
		puts(result);
		return;
	}

	for(i=0;i<n;i++)
	{
		if(i>0&&word[i]==word[i-1]&&!visit[i-1])   //剪枝：如果当前字母i与其前一个字母i-1相同，且字母i-1未被访问，则跳过
			continue;
		if(!visit[i])           
		{
			visit[i]=1;
			result[depth]=word[i];
			dfs(depth+1);       
			visit[i]=0;
		}
	}
}

int main()
{
	int num_word;
	scanf("%d",&num_word);
	while(num_word--)
	{
		scanf("%s",word);
		n=strlen(word);
		qsort(word,n,sizeof(char),cmp);
		memset(visit,0,sizeof(visit));
		dfs(0);
	}
	return 0;
}