概述
前言：迷宫问题很常见，若求最小路径，一般用广度优先搜索，主要要注意几点：
1）对新加四个方向符合要求的位置到队列时，判断是否被访问过，INF代表未被访问 d[nx][ny] == INF2）到达终点的最小距离的表达式
d[nx][ny] = d[p.first][p.second] + 1;
3）存新的位置position(x,y)的定义，用pair不用maptypedef pair<int, int> position;
4）新的四个方向的位置的定义
int dx[4] = {1, 0,-1, 0}; // 左右方向
int dy[4] = {0, 1, 0, -1}; // 上下方向
for (i = 0; i < 4; i++) { // 新的位置的定义
int nx = p.first + dx[i];
int ny = p.second + dy[i];
...
}
题目：
/*
* 对于每个输入文件,第一行输入一个整数N(1<=N<=500),接下来N行,每行N个字符,表示这个迷宫的状态.
* 其中’S’表示小华的位置,’E’表示终点,’#’表示障碍物,’.’表示可以走的地方.
* Input: 3
#S#
...
E##
Output: 3
思路：
1.从起点开始，先将其加入队列，设置距离为0；
2.从队列首端取出位置，将从这个位置能够到达的四个方向的位置加入队列，并且让这些位置的距离为上一个位置的距离加上1；
3.循环2直到将终点添加到队列中，这说明我们已经找到了路径；
*/#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
char INF = 0x3f3f3f3f; // 初始化时，队列存新的位置position(x,y)的值都为INF,对待放入队列的位置进行判断是否访问过
int d[3][3] = {0}; // 这里的值是可变的，由输入决定
typedef pair<int, int> position; // 存新的位置position(x,y)
void BFS(vector<vector<char>> &matrix, int x, int y, int Ex, int Ey) {
if ((x < 0) || (y < 0) || (x >= matrix.size()) || (y >= matrix[0].size()) || matrix[x][y] == '#') {
return;
}
queue<position> q;
q.push(position(x, y));
d[x][y] = 0; // 从起点出发将距离设为0，并放入队列首端
int dx[4] = {1, 0,-1, 0}; // 左右方向
int dy[4] = {0, 1, 0, -1}; // 上下方向
int i;
int index = 4;
while (!q.empty()) {
auto p = q.front();
q.pop();
for (i = 0; i < 4; i++) {
int nx = p.first + dx[i];
int ny = p.second + dy[i];
if (nx >= 0 && nx < matrix.size() && matrix[nx][ny] != '#' && d[nx][ny] == INF) { // 如果四个新的方向都没访问过
q.push(position(nx, ny)); // 往队列中插入新的四个方向
d[nx][ny] = d[p.first][p.second] + 1; // 距离加1
}
if (nx == Ex && ny == Ey) { // 如果到了终点，跳出循环，不再往队列中插入新的四个方向的位置
break;
}
}
if (i != index) { break; }
}
}
int main()
{
vector<vector<char>> matrix = {{'#', 'S', '#'},{'.', '.', '.'},{'E', '#', '#'}};
int startX, startY, endX, endY;
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[0].size(); j++) {
d[i][j] = INF;
if (matrix[i][j] == 'S') {
startX = i;
startY = j;
}
if (matrix[i][j] == 'E') {
endX = i;
endY = j;
}
}
}
BFS(matrix, startX, startY, endX, endY); // 广度优先搜索
cout << d[endX][endY] << endl; // 寻找到底终点的最短路径
return 0;
} #include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <queue>
using namespace std;
// 第一题：给定一个闭区间范围[m, n]，1<=m<=n<=10^9，求[m,n]区间上位数为偶数的整数有多少个？
// 输入样例：m = 1, n = 100
// 输出样例：90
// 输出样例说明：[1,100]区间上，有10~99这些整数的位数是2位，是偶数，所以答案是10~99这些整数的数量，即90。
// 思路： 先判断m是哪个区间内，再判断n是哪个区间内，
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int mostDouble2(int m, int n) {
vector<pair<int, int>> numbers;
numbers.push_back(make_pair(10, 99));
numbers.push_back(make_pair(100, 999));
numbers.push_back(make_pair(1000, 9999));
numbers.push_back(make_pair(100000, 999999));
numbers.push_back(make_pair(10000000, 99999999));
numbers.push_back(make_pair(1000000000, 1000000001));
int finalNum = 0;
cout << "---1-----" << endl;
for (auto num:numbers) {
int left = num.first;
int right = num.second;
cout << "---2-----" << left << right << endl;
// 目标区间落在当前区间内
if (m >= left && n <= right) {
cout << "---3-----" << left << right << endl;
return n - m + 1;
}
// 目标区间被当前区间bufen 包含
if (m < left && n > right) {
return right - left + 1;
}
// 计算右侧重叠区间长度（不满足第一个判断条件，则n一定大于rightNum）
if (m >= left && m <= right) {
return right - m + 1;
}
// 计算左侧重叠区间长度(不满足第一个判断条件，则m一定小于leftNum)
if (n >= left && n <= right) {
return n - left + 1;
}
}
}
// 一个机房里面有N个位置可以放N个服务器，每个服务器都有一个标签，标签为正整数1~N，且有可能有重复。
// 输入一个标签列表（无序的），求最少移动多少个服务器可以让标签列表有序。
// 输入样例：[1,1,2,3,5,4]
// 输出样例：2
// 输出样例说明：互换标签为5和4的服务器，即可使得标签列表有序
int minTrans(vector<int> &trans) {
vector<int> sortedTrans(trans);
int resultNum = 0;
sort(sortedTrans.begin(), sortedTrans.end());
for (int i = 0; i < trans.size(); i++) {
if (trans[i] != sortedTrans[i]) {
resultNum++;
}
}
return resultNum;
} // 第三题 某地突发一起重大交通事故，热心群众立即播打了120急救电话，事发时段正巧是下班高峰，路况不尽如人意。
// 救护车司机打开地图matrix，matrix是给定的一个的矩阵，给定起点S（坐标 startX, startY）以及终点E（坐标 endX, endY）。
// 地图上所有的0 都显示通畅路段，1 代表拥堵路段（拥堵路段不可通行）。为了能尽快将伤员送往医院，
// 司机立即求助于市交通部指挥中心，指挥中心使用智慧交通提供的紧急救援功能，可以将地图上的一个拥堵路段（1）
// 开辟出一道绿色通道变为通畅路段（0）。（注意：司机仅有一次开辟绿色通道的机会）司机一次只能往上、往下、往左、往右行驶一公里
// ，请返回他从S开始并走到E所花的最短公里数。如果一定不能到达，请返回-1。
//输入：matrix = [[0,0,1,0],[1,0,0,0]], startX = 0, startY = 0, endX = 0, endY = 3
//输出：3
//解释：司机在智慧交通提供的紧急救援功能的引导下可以将坐标为 (0, 2) 的拥堵路段开辟出一道绿色通道转变为通畅路段。
// 这样的公里数最少，为 3。
//输入：matrix = [[0,1,1,0],[1,0,0,0]], startX = 0, startY = 0, endX = 0, endY = 3
//输出：5
//解释：司机在智慧交通提供的紧急救援功能的引导下只能将坐标为(1, 0)的拥堵路段开辟出一条绿色通道变为通畅路段。
// 这样的公里数为5。
//输入：matrix = [[0,1,1,0],[1,1,0,0]], startX = 0, startY = 0, endX = 0, endY = 3
//输出：-1
//解释：司机被困在了起点。答案为-1。
//限制：
//matrix 大小不超过 100 * 100
//0 <= 拥堵路段（1）的个数 <= 50
//起始点和终点都不是拥堵路段。
// DFS解法 ： 使用一个bool变量hasGreenPathUsed来记录是否已使用清除路障，使用一个二维数组visited来记录是否访问过，
// 使用一个int变量curMinStepNumber来存储当前的最短路径，然后利用常用的回溯法去遍历每一条可能到达的路径，并记录其路径长度，
// 与当前的最小路径长度做比较通过剪枝：当前路径长度已超过当前最小路径长度，即后续的路径探索也不会得到一个更短的路径。
vector<pair<int, int>> nextPos;
int curMinStepNumber = 49999;
int finalPosX;
int finalPosY;
vector<vector<int>> visited;
void getnextPos() {
nextPos.push_back(make_pair(0, 1));
nextPos.push_back(make_pair(1, 0));
nextPos.push_back(make_pair(-1, 0));
nextPos.push_back(make_pair(0, -1));
}
void findThePath(vector<vector<int>> &matrix, int startX, int startY, int curStepNumber, bool hasGreenPathUsed) {
if (startX == finalPosX && startY == finalPosY) {
curMinStepNumber = curStepNumber < curMinStepNumber ? curStepNumber : curMinStepNumber;
} else {
// 进行剪枝
if (curStepNumber < curMinStepNumber) {
for (auto next : nextPos) {
int nextX = startX + next.first;
int nextY = startY + next.second;
if (nextX >= 0 && nextX < matrix.size() && nextY >= 0 && nextY < matrix[0].size() &&
!visited[nextX][nextY]) {
visited[nextX][nextY] = 1;
if (matrix[nextX][nextY] == 1) {
if (!hasGreenPathUsed) {
findThePath(matrix, nextX, nextY, curStepNumber + 1, true);// 清除当前路障
}
} else {
findThePath(matrix, nextX, nextY, curStepNumber + 1, hasGreenPathUsed);
}
visited[nextX][nextY] = 0;// 回溯
}
}
}
}
} int rescue(vector<vector<int>> &matrix, int startX, int startY, int endX, int endY) {
for (int i = 0; i < matrix.size(); i++) {
vector<int> tempVec(matrix[0].size(), 0);
visited.push_back(tempVec);
}
getnextPos();
finalPosX = endX;
finalPosY = endY;
visited[startX][startY] = 1;
findThePath(matrix, startX, startY, 0, false);
return curMinStepNumber < 49999 ? curMinStepNumber : -1;
}
// BFS 解法： 用一个队列来存3元组
vector<pair<int, int>> getNextVec() {
vector<pair<int, int>> nextPos;
nextPos.push_back(make_pair(0, 1));
nextPos.push_back(make_pair(1, 0));
nextPos.push_back(make_pair(-1, 0));
nextPos.push_back(make_pair(0, -1));
return nextPos;
}
int rescue1(vector<vector<int>> &matrix, int startX, int startY, int endX, int endY) {
vector<pair<int, int>> nextPos = getNextVec();
vector<vector<int>> visitedWithShield(matrix.size(), vector<int>(matrix[0].size(), 0));
vector<vector<int>> visitedNoShield(matrix.size(), vector<int>(matrix[0].size(), 0));
queue<tuple<int, int, int>> paths; // 需要保存3个及以上的数据时就需要使用tuple元组
paths.push(make_tuple(startX, startY, 0));
int shortestPath = 0;
while (!paths.empty()) {
shortestPath++;
int size = paths.size();
while (size-- > 0) {
int curX = get<0>(paths.front());
int curY = get<1>(paths.front());
int isShiledUsed = get<2>(paths.front());
paths.pop();
if (curX == endX && curY == endY) {
return shortestPath - 1;
}
for (auto next : nextPos) {
int nextX = curX + next.first;
int nextY = curY + next.second;
if (nextX >= 0 && nextX < matrix.size() && nextY >= 0 && nextY < matrix[0].size()) {
if (matrix[nextX][nextY] == 1) {
// 下一个位置有路障，同时清除路障还没用过，且下个位置不是清障走过的位置
if (isShiledUsed == 0 && !visitedWithShield[nextX][nextY]) {
paths.push(make_tuple(nextX, nextY, 1));
visitedWithShield[nextX][nextY] = 1;
}
} else {
// 下个位置不是路障，没用过路障清除或者用过路障清除都是可以继续走下去的
if ((isShiledUsed == 0 && !visitedNoShield[nextX][nextY]) ||
(isShiledUsed == 1 && !visitedWithShield[nextX][nextY])) {
paths.push(make_tuple(nextX, nextY, isShiledUsed));
if (isShiledUsed == 0) {
visitedNoShield[nextX][nextY] = 1;
} else {
visitedWithShield[nextX][nextY] = 1;
}
}
}
}
}
}
}
return -1;
}
/* 19. 水域大小 你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。
* 由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
输入：
[
[0,2,1,0],
[0,1,0,1],
[1,1,0,1],
[0,1,0,1]
]
输出： [1,2,4]
提示：
0 < len(land) <= 1000
0 < len(land[i]) <= 1000
思路：利用深度搜索，每次遇到land[i][j]为0,进行一次DFS，count 加1，
方向数组为dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[8] = {1, 1, 0, -1, -1, -1, 0, 1},
利用land[x][y] = -1来染色，表示已经访问过
* */
vector<int> pondSizes(vector<vector<int>> &land) {
vector<int> result;
for (int i = 0; i < land.size(); ++i) {
for (int j = 0; j < land[i].size(); ++j) {
if (land[i][j] == 0) {
int count = 0;
dfs(i, j, count, land); // 有效的一次dfs
if (count != 0) { // 计算鱼塘大小
result.push_back(count);
}
}
}
}
sort(result.begin(), result.end());
return result;
}
void dfs(int x, int y, int &count, vector<vector<int>> &land) {
land[x][y] = -1; // 染色
count++;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[8] = {1, 1, 0, -1, -1, -1, 0, 1}; //方向数组
for (int i = 0; i < 8; ++i) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX >= 0 && newX < land.size() && newY >= 0 && newY < land[0].size() && land[newX][newY] == 0) {
dfs(newX, newY, count, land);
}
}
}
/* 04. 检查二叉树平衡性
* 实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。
* 给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/
2 2
/
3 3
/
4 4
返回 false 。
* */
bool flag = true;
bool isBalanced(TreeNode *root) {
dfs(root);
return flag;
}
int dfs(TreeNode *root) {
if (!root) return 0;
int left = dfs(root->left);
int right = dfs(root->right);
if (abs(left - right) > 1) {
flag = false;
}
return max(left, right) + 1;
}
/* 695. 岛屿的最大面积 给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。
你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
思路：
1）先排除全为0的情况，返回最大岛屿面积0
2）从岛屿的grid[i][j]=1开始，依次对当前坐标的垂直和水平四个方向进行深度搜索，每次DFS遇到land[newX][newY] == 1，面积count加1，
然后把每条路径的结果存于vector中，按照从大到小对vector排序，取vector第一个值为返回结果。
3）采用land[x][y] = -1进行染色，表示已经访问过。
* */
int maxAreaOfIsland(vector<vector<int>> &grid) {
vector<int> vec;
int cnt = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 0) {
cnt++;
}
}
}
if (cnt == (grid.size() * grid[0].size())) {
return 0;
}
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[i].size(); ++j) {
int count = 0;
if (grid[i][j] == 1) {
DFS(i, j, count, grid); // 有效的一次dfs
if (count != 0) { // 计算大小
vec.push_back(count);
}
}
}
}
sort(vec.begin(), vec.end(), greater<int>());
return vec[0];
}
void DFS(int x, int y, int &count, vector<vector<int>> &land) {
land[x][y] = -1; // 染色
count++;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; //方向数组
for (int i = 0; i < 4; ++i) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX >= 0 && newX < land.size() && newY >= 0 && newY < land[0].size() && land[newX][newY] == 1) {
DFS(newX, newY, count, land);
}
}
}
/* 1254. 统计封闭岛屿的数目 有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。
我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。
如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。
请返回封闭岛屿的数目。即被 1 区域包围
* */
int closedIsland(vector<vector<int>> &grid) {
int count = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 0) {
if (DFS(i, j, grid)) {
count++;
}
}
}
}
return count;
}
bool DFS(int x, int y, vector<vector<int>> &land) {
if (x < 0 || x >= land.size() || y < 0 || y >= land[0].size()) {
return false; //是否到达边界，一次dfs搜索中只要有一个地方最终走到这儿就不是封闭岛屿了
}
if (land[x][y] != 0) { //如果是海洋或是已经访问过的陆地则返回false，因为这两种情况不需要继续遍历，且也没找到边界
return true;
}
land[x][y] = -1; // 染色
bool up = DFS(x - 1, y, land);
bool down = DFS(x + 1, y, land);
bool left = DFS(x, y - 1, land);
bool right = DFS(x, y + 1, land);
if (up && down && left && right) {
return true;
}
return false;
}
};
main函数
int main() {
Solution solution;
cout << "---------test1-------------" << endl;
int m = 1, n = 100;
cout << solution.mostDouble2(m, n) << endl;
cout << "---------test2-------------" << endl;
vector<int> trans = {1, 1, 2, 3, 5, 4};
cout << solution.minTrans(trans) << endl;
cout << "---------test3-------------" << endl;
vector<vector<int>> matrix = {{0, 0, 1, 0},
{1, 0, 0, 0}};
int startX = 0, startY = 0, endX = 0, endY = 3;
cout << solution.rescue(matrix, startX, startY, endX, endY) << endl; // 3
cout << "---------test 19. 水域大小 -------------" << endl;
vector<vector<int>> land = {{0, 2, 1, 0},
{0, 1, 0, 1},
{1, 1, 0, 1},
{0, 1, 0, 1}};
vector<int> poolSize = solution.pondSizes(land);
cout << poolSize[0] << poolSize[1] << poolSize[2] << endl; // {1,2,4}
cout << "---------test 04.检查二叉树平衡性 -------------" << endl;
// 初始化一棵树
TreeNode *root = new TreeNode(3);
TreeNode *b1 = new TreeNode(9);
TreeNode *b2 = new TreeNode(20);
TreeNode *c3 = new TreeNode(15);
TreeNode *c4 = new TreeNode(7);
root->left = b1;
root->right = b2;
b2->left = c3;
b2->right = c4;
vector<int> ret;
cout << solution.isBalanced(root) << endl; // {1,2,4}
cout << "---------test 695. 岛屿的最大面积 -------------" << endl;
vector<vector<int>> grid1 = {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
{0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
vector<vector<int>> grid = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
int maxArea = solution.maxAreaOfIsland(grid1);
cout << "maxArea: " << maxArea << endl; // {1,2,4}
cout << "---------test 1254. 统计封闭岛屿的数目 -------------" << endl;
vector<vector<int>> gridLand = {{0, 0, 1, 0, 0},
{0, 1, 0, 1, 0},
{0, 1, 1, 1, 0}};
int closedIslandNum = solution.closedIsland(gridLand);
cout << "closedIslandNum: " << closedIslandNum << endl; // 2
}
最后
以上就是时尚乌龟为你收集整理的leetcode之迷宫问题---BFS 广度优先搜索的全部内容，希望文章能够帮你解决leetcode之迷宫问题---BFS 广度优先搜索所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复