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://www.yijiale78.com/article22/ceijjc.html
成都網站建設公司_創新互聯，為您提供ChatGPT、面包屑導航、品牌網站設計、搜索引擎優化、網站收錄、做網站
聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯
- 網站建設完成之后如何選擇虛擬主機或者服務器 2016-10-19
- 虛擬主機流量會受到什么限制？ 2022-10-06
- 網站建設如何選擇性價比高的虛擬主機 2022-11-09
- 云服務器和虛擬主機的區別主要有哪些？ 2022-10-06
- 成都網站建設時該選擇服務器還是虛擬主機 2017-01-14
- 免費虛擬主機試用哪家好？三家提供虛擬主機試用的主機商推薦 2022-10-09
- 企業網站建設中選擇虛擬主機的秘訣 2022-05-02
- 網站建設之怎樣能更好地選擇虛擬主機 2016-08-12
- 如何選擇虛擬主機？ 2020-04-27
- 云服務器和虛擬主機的特點及其區別 2022-08-24
- 虛擬主機和云主機的區別是什么？ 2021-03-05
- 國外虛擬主機租用的優勢和特點是什么 2021-02-28