10深度搜索与广度搜索的应用题目-创新互联

深度优先搜索的题目

题目一：

成都创新互联公司服务项目包括丽江网站建设、丽江网站制作、丽江网页制作以及丽江网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，丽江网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到丽江省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

终止条件：当摆放到第n+1个盒子时，说明问题已经解决。

#includeusing namespace std;

int data[101];
int book[101];
int n = 0, sum = 0;
void fun(int step) {
	if (step == n + 1) {
		for (int i = 1; i<= n; i++) cout<< data[i]<< " ";
		cout<< endl;
		sum++;
		return;
	}
	for (int i = 1; i<= n; i++) {
		if (book[i] == 0) {
			data[i] = i;
			book[i] = 1;
			fun(step + 1);
			book[i] = 0;
		}
	}
}
int main() {
	cin >>n;
	fun(1);
	cout<< sum<< endl;
	return 0;
}

题目二：

终止条件：9张扑克牌都已放好，该放第10张扑克牌了。但是在输出结果时要判断等式是否成立

#includeusing namespace std;

int data[10];
int book[10];
int sum=0; 
void dfs(int step) {
	if (step == 10) {        //边界条件

		//满足条件 输出结果
		if (data[1] * 100 + data[2] * 10 + data[3] + data[4] * 100 + data[5] * 10 + data[6]\
		        == data[7] * 100 + data[8] * 10 + data[9]) {
			for (int i = 1; i<= 9; i++) cout<< data[i]<< " ";
			cout<< endl;
			sum++;
		}
		//返回上一层，继续循环 
		return;
	}

	for (int i = 1; i<= 9; i++) { //单层循环  罗列所有可能
		if (book[i] == 1) continue;

		book[i] = 1;
		data[step] = i;
		dfs(step + 1);
		book[i] = 0;
	}
}
int main() {
	dfs(1);
	cout<

题目三

终止条件：到达了小哈的位置

问题模型化：0代表空地，1代表障碍物

#includeusing namespace std;


int _map[5][4] = {{0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 0, 0, 1}};
int p = 3, q = 2; //终点位置

int _next[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //四个拓展方向
int _book[5][4] = {0}; //记录已经走过的点

int step = 0, min_step = 1000; //记录走的步数
int xy[20][2] = {0};       //每一步走情况
int min_xy[20][2] = {0};   //最少走的步数


void dfs(int x, int y) {
	if (x == p && y == q) { //终止条件
		//找到了一条路，但不一定是最短的路
		if (step< min_step) {
			min_step = step;
			for (int i = 0; i<= min_step; i++) {
				min_xy[i][0] = xy[i][0];
				min_xy[i][1] = xy[i][1];
			}
		}
		return;
	}
	for (int i = 0; i<= 3; i++) { //罗列以(x,y)为起点下可以到达的下一个点
		int next_x = x + _next[i][0];
		int next_y = y + _next[i][1];
		if (_map[next_x][next_y] == 1) continue; //该点是障碍物
		if (_book[next_x][next_y] == 1) continue; //该点已经走过
		if (next_x >= 5 || next_x< 0 || next_y >= 4 || next_y< 0) continue; //该点超过边界

		_book[next_x][next_y] = 1; //标记该点已经走过
		step++;
		xy[step][0] = next_x;    //记录中间结果
		xy[step][1] = next_y;
		dfs(next_x, next_y);
		step--;
		_book[next_x][next_y] = 0; //标记该点已经走过

	}
	return;
}
int main() {
	dfs(0, 0);
	cout<< min_step<< endl;
	for(int i=0;i<=min_step;i++){
		cout<

广度优先搜索的题目题目一
#includeusing namespace std;


int _map[5][4] = {{0, 0, 1, 0}, {0, 0, 0, 0}, {0, 0, 1, 0}, {0, 1, 0, 0}, {0, 0, 0, 1}};
int p = 3, q = 2; //终点位置

int _next[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //四个拓展方向
int _book[5][4] = {0}; //记录已经走过的点


struct node {
	int x;
	int y;
	int step;
	int f;
};

struct node que[30];
int head, tail;

bool bfs(int x, int y) {
	//初始化队列
	head = 1;
	tail = 1;
	que[tail].x = x;
	que[tail].y = y;
	que[tail].step = 0;
	que[tail].f = 0;
	_book[0][0] = 1;
	tail++;

	bool flag = 0; //是否到达终点

	while (head< tail) { //队列不为空
		for (int i = 0; i<= 3; i++) { //列举周围的点
			int current_x = que[head].x + _next[i][0];
			int current_y = que[head].y + _next[i][1];
			if (_map[current_x][current_y] == 1) continue; //该点为障碍物
			if (_book[current_x][current_y] == 1) continue; //该点为已走点
			if (current_x >= 5 || current_x< 0 || current_y >= 4 || current_y< 0) continue; //超过边界
			//满足所有情况，加入队列
			que[tail].x = current_x;
			que[tail].y = current_y;
			que[tail].step = que[head].step + 1;
			que[tail].f = head;
			tail++;
			_book[current_x][current_y] = 1;
			//判断是否已经到达终点
			if (current_x == p && current_y == q) {
				flag = 1;
				break;
			}
		}
		if (flag == 1) break; //说明达到终点
		head++;
	}

	return flag;
}
int main() {
	if (bfs(0, 0)) {
		tail--;
		//输出步数
		cout<< que[tail].step<< endl;
		//输出路径
		cout<< que[tail].x<< ","<< que[tail].y<< endl;
		int next_f = que[tail].f;
		while (next_f != 0) {
			cout<< que[next_f].x<< ","<< que[next_f].y<< endl;
			next_f = que[next_f].f;
		}
	}
	else
		cout<< "no"<< endl;
	return 0;
}
综合应用  炸弹人
广度优先搜索的程序实现：
#includeusing namespace std;


int m = 13, n = 13; //地图的尺寸大小
//地图的信息 0代表空地 1代表障碍或墙 2代表敌人

int _map[13][13] = {
	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
	{1, 2, 2, 0, 2, 2, 2, 1, 2, 2, 2, 0, 1},
	{1, 1, 1, 0, 1, 2, 1, 2, 1, 2, 1, 2, 1},
	{1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 1},
	{1, 2, 1, 0, 1, 1, 1, 0, 1, 2, 1, 2, 1},
	{1, 2, 2, 0, 2, 2, 2, 0, 1, 0, 2, 2, 1},
	{1, 2, 1, 0, 1, 2, 1, 0, 1, 0, 0, 0, 1},
	{1, 1, 2, 0, 0, 0, 2, 0, 0, 0, 1, 0, 1},
	{1, 2, 1, 0, 1, 2, 1, 1, 1, 0, 1, 2, 1},
	{1, 0, 0, 0, 2, 1, 2, 2, 2, 0, 2, 2, 1},
	{1, 2, 1, 0, 1, 2, 1, 2, 1, 0, 1, 2, 1},
	{1, 2, 2, 0, 2, 2, 2, 1, 2, 0, 2, 2, 1},
	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

int p = 3, q = 3; //小人的起点位置

int _next[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //四个拓展方向
int _book[20][20] = {0}; //记录已经走过的点


struct node {
	int x;
	int y;
};

struct node que[200]; //扩展队列
int head, tail;       //队列的首和尾


int get_sum(int x, int y) { //获得杀死敌人的数量
	int _sum = 0;
	int i, j;

	i = x, j = y;
	while (_map[i][j] != 1) {
		if (_map[i][j] == 2)_sum++;
		i++;
	}
	i = x, j = y;
	while (_map[i][j] != 1) {
		if (_map[i][j] == 2)_sum++;
		i--;
	}
	i = x, j = y;
	while (_map[i][j] != 1) {
		if (_map[i][j] == 2)_sum++;
		j++;
	}
	i = x, j = y;
	while (_map[i][j] != 1) {
		if (_map[i][j] == 2)_sum++;
		j--;
	}
	return _sum;
}

int max_sum=0;
int max_x=0;
int max_y=0;

void bfs(int x, int y) {
	int current_sum=0;
	//初始化队列与当前消灭的敌人 
	head = 1;
	tail = 1;
	max_x=que[tail].x = x;
	max_y=que[tail].y = y;
	max_sum=get_sum(x,y);
	_book[x][y] = 1;
	tail++;
	
	while (head< tail) { //队列不为空
		for (int i = 0; i<= 3; i++) { //列举周围的点
			int current_x = que[head].x + _next[i][0];
			int current_y = que[head].y + _next[i][1];
			if (_map[current_x][current_y] == 1 || _map[current_x][current_y] == 2) continue; //该点为障碍物
			if (_book[current_x][current_y] == 1) continue; //该点为已走点
			if (current_x >= 13 || current_x< 0 || current_y >= 13 || current_y< 0) continue; //超过边界
			//满足所有情况，加入队列
			que[tail].x = current_x;
			que[tail].y = current_y;
			current_sum=get_sum(current_x,current_y);
			if(current_sum>max_sum){
				max_sum=current_sum;
				max_x=current_x;
				max_y=current_y;
			}
			tail++;
			_book[current_x][current_y] = 1;
		}
		head++;
	}
}
int main() {
	bfs(p, q);
//	max_sum=get_sum(7,11);
	cout<
深度优先的程序实现
#includeusing namespace std;


int m = 13, n = 13; //地图的尺寸大小
//地图的信息 0代表空地 1代表障碍或墙 2代表敌人

int _map[13][13] = {
	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
	{1, 2, 2, 0, 2, 2, 2, 1, 2, 2, 2, 0, 1},
	{1, 1, 1, 0, 1, 2, 1, 2, 1, 2, 1, 2, 1},
	{1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 1},
	{1, 2, 1, 0, 1, 1, 1, 0, 1, 2, 1, 2, 1},
	{1, 2, 2, 0, 2, 2, 2, 0, 1, 0, 2, 2, 1},
	{1, 2, 1, 0, 1, 2, 1, 0, 1, 0, 1, 0, 1},
	{1, 1, 2, 0, 0, 0, 2, 0, 0, 0, 1, 0, 1},
	{1, 2, 1, 0, 1, 2, 1, 1, 1, 0, 1, 2, 1},
	{1, 0, 0, 0, 2, 1, 2, 2, 2, 0, 2, 2, 1},
	{1, 2, 1, 0, 1, 2, 1, 2, 1, 0, 1, 2, 1},
	{1, 2, 2, 0, 2, 2, 2, 1, 2, 0, 2, 2, 1},
	{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

int p = 3, q = 3; //小人的起点位置

int _next[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //四个拓展方向
int _book[20][20] = {0}; //记录已经走过的点


struct node {
	int x;
	int y;
};

int get_sum(int x, int y) { //获得杀死敌人的数量
	int _sum = 0, i, j;

	i = x, j = y;
	while (_map[i][j] != 1) {
		if (_map[i][j] == 2)_sum++;
		i++;
	}
	i = x, j = y;
	while (_map[i][j] != 1) {
		if (_map[i][j] == 2)_sum++;
		i--;
	}
	i = x, j = y;
	while (_map[i][j] != 1) {
		if (_map[i][j] == 2)_sum++;
		j++;
	}
	i = x, j = y;
	while (_map[i][j] != 1) {
		if (_map[i][j] == 2)_sum++;
		j--;
	}
	return _sum;
}

int max_sum = 0;
int max_x = 0;
int max_y = 0;

void dfs(int x, int y) {
	int current_sum = 0;
	for (int i = 0; i<= 3; i++) {        //列举周围的点
		int current_x = x + _next[i][0];
		int current_y = y + _next[i][1];
		if (_map[current_x][current_y] == 1 || _map[current_x][current_y] == 2) continue; //该点为障碍物或者敌人
		if (_book[current_x][current_y] == 1) continue; //该点为已走点
		if (current_x >= m || current_x< 0 || current_y >= n || current_y< 0) continue; //超过边界
		current_sum = get_sum(current_x, current_y);
		if (current_sum >max_sum) {
			max_sum = current_sum;
			max_x = current_x;
			max_y = current_y;
//			cout<
综合应用  宝岛探险
广度优先搜索的程序实现
#includeusing namespace std;

int _map[10][10] = { //地图信息
	{1, 2, 1, 0, 0, 0, 0, 0, 2, 3},
	{3, 0, 2, 0, 1, 2, 1, 0, 1, 2},
	{4, 0, 1, 0, 1, 2, 3, 2, 0, 1},
	{3, 2, 0, 0, 0, 1, 2, 4, 0, 0},
	{0, 0, 0, 0, 0, 0, 1, 5, 3, 0},
	{0, 1, 2, 1, 0, 1, 5, 4, 3, 0},
	{0, 1, 2, 3, 1, 3, 6, 2, 1, 0},
	{0, 0, 3, 4, 8, 9, 7, 5, 0, 0},
	{0, 0, 0, 3, 7, 8, 6, 0, 1, 2},
	{0, 0, 0, 0, 0, 0, 0, 0, 1, 0}
};
struct node { //队列变量
	int x;
	int y;
};
struct node _queue[105];
int head, tail;

int sum = 0;  //统计点的个数
int _book[10][10] = {0}; //避免点的重复计数
int _next[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; //设定拓展方向

void bfs() {
	while (head< tail) {
		//分层枚举拓展
		for (int i = 0; i<= 3; i++) {
			int current_x = _queue[head].x + _next[i][0];
			int current_y = _queue[head].y + _next[i][1];
			//重复判断
			if (_book[current_x][current_y] == 1) continue;
			//海洋判断
			if (_map[current_x][current_y] == 0) continue;
			//边界判断
			if (current_x >= 10 || current_x< 0 || current_y >= 10 || current_y< 0) continue;
			//当前点满足要求 加入队列，统计信息
			_queue[tail].x = current_x;
			_queue[tail].y = current_y;
			_book[current_x][current_y] = 1;
			tail++;
			sum++;
		}
		head++;
	}
}
int main() {
	int p = 5, q = 7;
	//队列初始化
	head = tail = 1;
	_queue[tail].x = p;
	_queue[tail].y = q;
	_book[p][q] = 1;
	sum++;
	tail++;
	bfs();
	cout<< sum<< endl;
	return 0;
}
注意实现：
1、队列的初始化放在while循环的外面
2、每次拓展的中点为head指向的当前点
深度优先搜索的程序实现
#includeusing namespace std;

int _map[10][10] = { //地图信息
	{1, 2, 1, 0, 0, 0, 0, 0, 2, 3},
	{3, 0, 2, 0, 1, 2, 1, 0, 1, 2},
	{4, 0, 1, 0, 1, 2, 3, 2, 0, 1},
	{3, 2, 0, 0, 0, 1, 2, 4, 0, 0},
	{0, 0, 0, 0, 0, 0, 1, 5, 3, 0},
	{0, 1, 2, 1, 0, 1, 5, 4, 3, 0},
	{0, 1, 2, 3, 1, 3, 6, 2, 1, 0},
	{0, 0, 3, 4, 8, 9, 7, 5, 0, 0},
	{0, 0, 0, 3, 7, 8, 6, 0, 1, 2},
	{0, 0, 0, 0, 0, 0, 0, 0, 1, 0}
};

int sum = 0;  //统计点的个数
int _book[10][10] = {0}; //避免点的重复计数
int _next[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; //设定拓展方向

void dfs(int x,int y) {
	//枚举所有的周围点 
	for (int i = 0; i<= 3; i++) {
		int current_x = x + _next[i][0];
		int current_y = y + _next[i][1];
		//重复判断
		if (_book[current_x][current_y] == 1) continue;
		//海洋判断
		if (_map[current_x][current_y] == 0) continue;
		//边界判断
		if (current_x >= 10 || current_x< 0 || current_y >= 10 || current_y< 0) continue;
		
		_book[current_x][current_y]=1;
		sum++;
		dfs(current_x,current_y);
		
	}
}
int main() {
	int p = 5, q = 7;
	dfs(p, q);
	cout<< sum<< endl;
	return 0;
}
注意事项：
1、此处是统计所有的点，递归完成后不需要退回，一直标记为走过的点就可以。
2、拓展方向没有要求。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
            

            分享名称：10深度搜索与广度搜索的应用题目-创新互联            

            分享地址：http://jkwzsj.com/article/ceijjc.html


    
        其他资讯
        
            
                    PHP7如何传参与返回值
                

                    javascript是不是动态的语言
                

                    Laravel5中怎么实现多个视图共享数据
                

                    怎么用java正则表达式检测电话号码和身份号码合法性
                

                    Sublimetext3配置LiveReload插件的方法