寬度有限搜索BFS搜索
B3625 迷宮尋路
題面
題目描述
機器貓被困在一個矩形迷宮里。
迷宮可以視為一個?n×m?矩陣，每個位置要么是空地，要么是墻。機器貓只能從一個空地走到其上、下、左、右的空地。
機器貓初始時位于?(1,1) 的位置，問能否走到?(n,m)?位置。
輸入格式
第一行，兩個正整數 n,m。
接下來?n?行，輸入這個迷宮。每行輸入一個長為?m?的字符串，#?表示墻，.?表示空地。
輸出格式
僅一行，一個字符串。如果機器貓能走到 (n,m)，則輸出?Yes；否則輸出?No。
輸入輸出樣例
輸入 #1?
3 5 .##.# .#... ...#.
輸出 #1?
Yes
說明/提示
樣例解釋
路線如下：(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)
題解
BFS的思路是從標點(1,1)開始逐層往外擴展，此時我們選擇建立一個隊列用來保存待訪問的點，只要隊列非空，判斷越界情況和其他非法情況后一直訪問相鄰位置，可以用一個結構組表示x,y坐標。為了避免重復訪問的情況，我們使用vis函數。訪問一個點后把vis[x][y]負值與1。到最后如果隊列的某個點到了(n,m) 終點，答案設為true，輸出這個情況YES。
代碼
#include <bits/stdc++.h>
using namespace std;int n, m, isOk;
char a[105][105];
bool vis[105][105];struct Pos {int x, y;Pos(int ax, int ay) {x = ax, y = ay;}
};void bfs() {queue<Pos> q;q.push(Pos(1, 1));while(!q.empty()) {Pos now = q.front();q.pop();int x = now.x, y = now.y;if(x < 1 || x > n) continue;if(y < 1 || y > m) continue;if(a[x][y] == '#') continue;if(vis[x][y]) continue;vis[x][y] = 1;if(x == n && y == m) isOk = true;q.push(Pos(x + 1, y));q.push(Pos(x - 1, y));q.push(Pos(x, y + 1));q.push(Pos(x, y - 1));}}int main() {cin >> n >> m;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> a[i][j];bfs();if(isOk)cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}P1451 求細胞數量
題面
題目描述
一矩形陣列由數字?0?到?9?組成，數字?1?到?9?代表細胞，細胞的定義為沿細胞數字上下左右若還是細胞數字則為同一細胞，求給定矩形陣列的細胞個數。
輸入格式
第一行兩個整數代表矩陣大小 n?和?m。
接下來?n?行，每行一個長度為?m?的只含字符?0?到?9?的字符串，代表這個?n×m?的矩陣。
輸出格式
一行一個整數代表細胞個數。
輸入輸出樣例
輸入 #1
4 10 0234500067 1034560500 2045600671 0000000089
輸出 #1
4
題解
這道題的意思，只要相鄰的數不是0，那么它和其他相鄰的數構成一個細胞，例如樣例中的12是一個細胞，23453456456是一個細胞，67，567189，一共四個細胞。這一道題可以用BFS也能用DFS搜索方法。在隊列非空的狀態依次判斷非法情況，避免重復訪問，判斷是否到終點并尋找答案，繼續訪問相鄰位置。在main循環中bfs之前要判斷這個數是否是細胞，是否訪問過。Vis可以當訪問數組的同時在這類題當成染色“Flood Fill”?
注意事項：
- 若（x,y）是細胞且無色，則答案＋1、并將其所屬整個細胞染色
- BFS 的實現 ：當隊列非空，訪問隊首，并將相鄰結點人隊?
代碼
#include <bits/stdc++.h>
using namespace std;
int n, m, ans;
char a[105][105];
bool vis[105][105];
struct Pos {int x, y;Pos(int ax = 0, int ay = 0) {x = ax; // 該結點的 x 值初始化為 axy = ay; // 該結點的 y 值初始化為 ay}
};
// 從 (x, y) 開始 BFS 整個細胞
void bfs(int x, int y) {queue<Pos> q;q.push(Pos(x, y)); // 將 (x,y) 入隊while(!q.empty()) { // 當隊列非空Pos now = q.front(); // 現在處理隊首結點q.pop(); // 隊首出隊int x = now.x, y = now.y;if(x < 1 || x > n) continue;if(y < 1 || y > m) continue;if(a[x][y] == '0') continue; // 不是細胞點if(vis[x][y]) continue; // 如果這個點被訪問過則跳過vis[x][y] = 1; // 用 vis 數組避免重復訪問q.push(Pos(x+1, y)); // 將上方結點加入到隊列q.push(Pos(x-1, y)); // 將下方結點加入到隊列q.push(Pos(x, y+1)); // 將左方結點加入到隊列q.push(Pos(x, y-1)); // 將右方結點加入到隊列}
}
int main() {cin >> n >> m;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> a[i][j];for(int x = 1; x <= n; x++)for(int y = 1; y <= m; y++)if(a[x][y]!='0'&& vis[x][y]==0) { // (x,y) 這個點是細胞點，且未訪問過ans++;bfs(x,y); // 開始對 (x,y) 這個點進行 BFS}cout << ans << endl;return 0;
}B3626 跳躍機器人
題面
題目描述
地上有一排格子，共?n?個位置。機器貓站在第一個格子上，需要取第?n?個格子里的東西。
機器貓當然不愿意自己跑過去，所以機器貓從口袋里掏出了一個機器人！這個機器人的行動遵循下面的規則：
- 初始時，機器人位于?1 號格子
- 若機器人目前在?x?格子，那么它可以跳躍到 x?1,x+1,2x?里的一個格子（不允許跳出界）
問機器人最少需要多少次跳躍，才能到達?n?號格子。
輸入格式
僅一行，一個正整數，表示?n。
輸出格式
僅一行，一個正整數，表示最少跳躍次數。
輸入輸出樣例
輸入 #1
30
輸出 #1
6
輸入 #2
50
輸出 #2
7
輸入 #3
64
輸出 #3
6
輸入 #4
63
輸出 #4
8
說明/提示
樣例解釋
第一組樣例：
1→2→4→8→16→15→301→2→4→8→16→15→30
第二組樣例：
1→2→3→6→12→24→25→501→2→3→6→12→24→25→50
第三組樣例：
1→2→4→8→16→32→641→2→4→8→16→32→64
第四組樣例：
1→2→4→8→16→32→31→62→631→2→4→8→16→32→31→62→63
請注意在本組樣例中，63?不能通過?64?1 得到，因為格子總數為?63，沒有第?64?個格子。
題解
代碼
#include <bits/stdc++.h>
using namespace std;
struct Pos {int x, cost;Pos(int ax = 0, int acost = 0) {x = ax, cost = acost;}
};
int n;
bool vis[1000005];
void bfs() {int x=1, cost=0;queue <Pos> q;q.push(Pos(x,cost)); while(!q.empty()) {Pos now = q.front();q.pop();int x = now.x, cost = now.cost;if(x<1||x>n) // 處理越界，如果 x 不在 [1,n] 范圍內continue; if(vis[x]) // 用 vis 數組判斷重復continue; vis[x] = 1; // 用 vis 數組標記這個數字被訪問過if(x == n) {cout << cost << endl;return;}q.push(Pos(x-1, cost+1));q.push(Pos(x+1,cost+1));q.push(Pos(2*x, cost+1));}
}
int main() {cin >> n;bfs();return 0;
} 
