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