算法04|搜索

搜索基本公式

void bfs (int step)
{
	判断边界
	尝试每一种可能  for(i=1;i<=n;i++)
	{
		继续下一步  dfs(step +1);
	}
	返回
}

一个例子

include <stdio.h>
int a[10],book[10],total=0;

void dfs(int step)
{
	int i;
	if (step==n+1) {//如果站在第n+1个盒子面前，则表示前n个盒子已经放好扑克牌
			for(i=1;i<=n;i++)
				printf("%d",a[i]);
				printf("\n");
				return;//返回之前的一步
	}
	for(i=1;i<=n;i++)
	{
		if (book[i]==0) {//表示第i号扑克牌仍然在手上
			a[step]=i;
			book[i]=1;
			dfs(step+1);
			book[i]=0;
		}
	}
	return;
}
int main(){
	scanf("%d",&n);
	dfs(1);
	getchar();getchar();
	return 0;
}

迷宫问题

#include <stdio.h>
//迷宫问题
struct note
{
	int x;
	int y;
	int f;
	int s;
};
int main()
{
	struct note que[2501];//地图大小不超过50*50
	int a[51][51]={0},book[51][51]={0};
	int next[4][2] = { { 0, 1},
						{ 1, 0},
						{ 0, -1},
						{-1, 0} };
	int head, tail;
	int i,j,k,m,n,startx,starty,q,p,tx,ty,flag;
	
	scanf("%d %d",&n, &m);
	for(i=1; i<=n; i++)
		for(j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	scanf("%d %d %d %d",&startx, &starty,&p,&q);
	//队列初始化
	head=1;
	tail=1;
	//插入迷宫入口坐标
	que[tail].x=startx;
	que[tail].y=starty;
	que[tail].f=0;
	que[tail].s=0;
	tail++;
	book[startx][starty]=1;	
	flag=0;
	while (head<tail) {
		for(k=0;k<=3;k++)
		{
			tx=que[head].x+next[k][0];
			ty=que[head].y+next[k][1];
			//判断是否越界
			if (tx<1 || tx>n || ty<1 || ty>m) 
				continue;
				//判断是否是障碍物或已经在路径中
			if(a[tx][ty]==0 && book[tx][ty]==0)
			{
				book[tx][ty]=1;
				que[tail].x=tx;
				que[tail].y=ty;
				que[tail].f=head;
				que[tail].s=que[head].s+1;
				tail++;
			}
			//到达目标点
			if(tx==p && ty==q)
			{
				flag=1;
				break;
			}
		}
		if (flag==1) 
			break;
			head++;	
		
	}	
	printf("%d",que[tail-1].s);
	getchar();getchar();
	return 0;
}