第七周 BFS(广度优先搜索):733、127、130、317、505、529、1263、1197、815、934
广度优先模板
void bfs(){
queue<int>q;
q.push(source);
while(!q.empty()){
int val = q.front();
q.pop();
visited[q] = 1;
if(val 满足**条件){
q.push(val);
}
}
}
知乎专栏：https://zhuanlan.zhihu.com/p/62884729BFS
BFS(广度优先搜索)常用来解决最短路径问题，第一次遍历到目的节点时，所经历的路径是最短路径。几个要点：只能用来求解无权图的最短路径问题，队列：用来存储每一层遍历得到的节点 标记：对于遍历过的结点，应将其标记，以防重复访问。
733 图像渲染
class Solution {
public:
const int dx[4] = { 1, -1, 0, 0};
const int dy[4] = { 0, 0, 1, -1};
queue<pair<int,int>>q;
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
//1.判断sr,sc处颜色是否与newColor相同，相同直接返回image
if(image[sr][sc] == newColor){
return image;
}
int m = image.size();
int n = image[0].size();
int startColor = image[sr][sc];
q.emplace(sr,sc);
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
//对中心处颜色进行渲染
image[x][y] = newColor;
//对它四个方向与它相同的四个元素进行渲染
//注意这里在扩展后需要判断是否还在图片中，另外只有与中心相同像素值的才能继续渲染（入队)
for(int i = 0; i < 4; i++){
int mx = x + dx[i];
int my = y + dy[i];
if(mx >= 0 && mx < m && my >= 0 && my < n && image[mx][my] == startColor){
q.emplace(mx,my);
}
}
}
return image;
}
};
class Solution {
public:
int visited[200005]={0};
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
if(source==destination){
return true;
}
vector<vector<int>> e(n+5);
for(auto i:edges){
e[i[0]].push_back(i[1]);
e[i[1]].push_back(i[0]);
}
queue<int> q;
q.push(source);
while(!q.empty()){
int curr =q.front();
q.pop();
visited[curr]=1;
if(curr==destination){
return true;
}
for(auto j:e[curr]){
if(!visited[j]){
q.push(j);
visited[j]=1;
}
}
}
return false;
}
};
反向思维，和为sum，sum-各加数就应该为0；
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
if (root == nullptr) {
return false;
}
if (root->left == nullptr && root->right == nullptr) {
return sum == root->val;
}
return hasPathSum(root->left, sum - root->val) ||
hasPathSum(root->right, sum - root->val);
}
};
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
127三重for循环挑战失败！！！！！！！！！！！！！！！！
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int n = beginWord.size();
unordered_set<string>set(wordList.begin(),wordList.end());
unordered_set<string>visited;
queue<string>q;
int res = 0;
q.push(beginWord);
while(!q.empty()){
int len = q.size();
for(int i = 0; i < len; i++){
for(int j = 0; j < n; j++){
string s = q.front();
for(int k = 0; k < 26; k++){
s[j] = 'a'+k;
if(s == endWord){
return res;
}
if(set.count(s) && !visited.count(s)){
q.push(s);
visited.insert(s);
}
}
}
q.pop();
}
}
return 0;
}
};
主要是怎么记录长度
把每个建筑物到达每个空地的距离加在一起，取最小
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
if(grid.empty() || grid[0].empty()) {
return -1;
}
vector<vector<int>> res(grid.size(), vector<int>(grid[0].size()));
queue<pair<int, int>> q;
int m = grid.size();
int n = grid[0].size();
int curTurn = 0;
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(grid[i][j] == 1) {
q.push({i, j});
int dist = 0;
while(!q.empty()) {
int sz = q.size();
for(int k = 0; k < sz; ++k) {
pair<int, int> cur = q.front();
q.pop();
int x = cur.first;
int y = cur.second;
res[x][y] += dist;
if(x + 1 < m && grid[x + 1][y] == curTurn) {
q.push({x + 1, y});
grid[x + 1][y] = curTurn + 3;
}
if(x - 1 >= 0 && grid[x - 1][y] == curTurn) {
q.push({x - 1, y});
grid[x - 1][y] = curTurn + 3;
}
if(y + 1 < n && grid[x][y + 1] == curTurn) {
q.push({x, y + 1});
grid[x][y + 1] = curTurn + 3;
}
if(y - 1 >= 0 && grid[x][y - 1] == curTurn) {
q.push({x, y - 1});
grid[x][y - 1] = curTurn + 3;
}
}
++dist;
}
curTurn += 3;
}
}
}
int shortestDist = INT_MAX;
bool found = false;
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(grid[i][j] == curTurn) {
found = true;
shortestDist = min(shortestDist, res[i][j]);
}
}
}
return found ? shortestDist : -1;
}
};
public class Solution {
public int shortestDistance(int[][] maze, int[] start, int[] dest) {
int[][] distance = new int[maze.length][maze[0].length];
for (int[] row: distance)
Arrays.fill(row, Integer.MAX_VALUE);
distance[start[0]][start[1]] = 0;
int[][] dirs={{0, 1} ,{0, -1}, {-1, 0}, {1, 0}};
Queue < int[] > queue = new LinkedList < > ();
queue.add(start);
while (!queue.isEmpty()) {
int[] s = queue.remove();
for (int[] dir: dirs) {
int x = s[0] + dir[0];
int y = s[1] + dir[1];
int count = 0;
while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
x += dir[0];
y += dir[1];
count++;
}
if (distance[s[0]][s[1]] + count < distance[x - dir[0]][y - dir[1]]) {
distance[x - dir[0]][y - dir[1]] = distance[s[0]][s[1]] + count;
queue.add(new int[] {x - dir[0], y - dir[1]});
}
}
}
return distance[dest[0]][dest[1]] == Integer.MAX_VALUE ? -1 : distance[dest[0]][dest[1]];
}
}
class Solution {
public:
int dir_x[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int dir_y[8] = {1, 0, -1, 0, 1, -1, 1, -1};
void bfs(vector<vector<char>>& board, int sx, int sy) {
queue<pair<int, int>> Q;
vector<vector<int>> vis(board.size(), vector<int>(board[0].size(), 0));
Q.push({sx, sy});
vis[sx][sy] = true;
while (!Q.empty()) {
auto pos = Q.front();
Q.pop();
int cnt = 0, x = pos.first, y = pos.second;
for (int i = 0; i < 8; ++i) {
int tx = x + dir_x[i];
int ty = y + dir_y[i];
if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size()) {
continue;
}
// 不用判断 M，因为如果有 M 的话游戏已经结束了
cnt += board[tx][ty] == 'M';
}
if (cnt > 0) {
// 规则 3
board[x][y] = cnt + '0';
} else {
// 规则 2
board[x][y] = 'B';
for (int i = 0; i < 8; ++i) {
int tx = x + dir_x[i];
int ty = y + dir_y[i];
// 这里不需要在存在 B 的时候继续扩展，因为 B 之前被点击的时候已经被扩展过了
if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size() || board[tx][ty] != 'E' || vis[tx][ty]) {
continue;
}
Q.push(make_pair(tx, ty));
vis[tx][ty] = true;
}
}
}
}
vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
int x = click[0], y = click[1];
if (board[x][y] == 'M') {
// 规则 1
board[x][y] = 'X';
} else {
bfs(board, x, y);
}
return board;
}
};
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minesweeper/solution/sao-lei-you-xi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public:
int minPushBox(vector<vector<char>>& grid)
{
// pq，[0]当前状态最小推箱子次数 [1]人的坐标x [2]人的坐标y [3]箱子的坐标x [4]箱子的坐标y
priority_queue<vector<size_t>, vector<vector<size_t>>, greater<vector<size_t>>> pq;
size_t m = grid.size();
size_t n = grid[0].size();
vector<size_t> a(5, 0);
for (size_t x = 0; x < m; x++)
{
for (size_t y = 0; y < n; y++)
{
if (grid[x][y] == 'S')
{
a[1] = x;
a[2] = y;
grid[x][y] = '.';
}
else if (grid[x][y] == 'B')
{
a[3] = x;
a[4] = y;
grid[x][y] = '.';
}
}
}
pq.push(a);
set<vector<size_t>> dist;
dist.insert({ a[1], a[2], a[3], a[4] });
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
while (!pq.empty())
{
auto v = pq.top();
pq.pop();
for (int i = 0; i < 4; i++)
{
vector<size_t> next_s = { v[1] + dx[i], v[2] + dy[i] };
if (next_s[0] >= m || next_s[1] >= n || grid[next_s[0]][next_s[1]] == '#')
{
continue;
}
vector<size_t> next_b = { v[3], v[4] };
size_t d = v[0];
if (next_s == next_b)
{
next_b[0] += dx[i];
next_b[1] += dy[i];
if (next_b[0] >= m || next_b[1] >= n || grid[next_b[0]][next_b[1]] == '#')
{
continue;
}
d++;
}
if (grid[next_b[0]][next_b[1]] == 'T')
{
return (int)d;
}
if (dist.find({next_s[0], next_s[1], next_b[0], next_b[1]}) != dist.end())
{
continue;
}
dist.insert({ next_s[0], next_s[1], next_b[0], next_b[1] });
pq.push({ d, next_s[0], next_s[1], next_b[0], next_b[1] });
}
}
return -1;
}
};
struct Point {
int x;
int y;
int path;
};
struct Hash{
size_t operator()(const pair<int, int> &item) const {
return hash<int>()(item.first) ^ hash<int>()(item.second);
}
};
class Solution {
public:
int minKnightMoves(int x, int y)
{
int direction[8][2] = {{2, 1}, {-2, 1}, {1, 2}, {-1, 2}, {2, -1}, {-2, -1}, {1, -2}, {-1, -2}};
x = abs(x);
y = abs(y);
queue<Point> pointQueue;
unordered_set<pair<int, int>, Hash> visited;
pointQueue.push({0,0,0});
visited.insert({0,0});
while (!pointQueue.empty()) {
Point topUint = pointQueue.front();
if (topUint.x == x && topUint.y == y) {
return topUint.path;
}
pointQueue.pop();
for (auto &item : direction) {
int nx = topUint.x + item[0];
int ny = topUint.y + item[1];
/* 剪枝 */
if (nx > -2 && nx <= x + 2 && ny > -2 && ny <= y + 2 && !visited.count({nx, ny})) {
pointQueue.push({nx, ny, topUint.path + 1});
visited.insert({nx, ny});
}
}
}
return 0;
}
};
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
if (source == target) {
return 0;
}
int n = routes.size();
vector<vector<int>> edge(n, vector<int>(n));
unordered_map<int, vector<int>> rec;
for (int i = 0; i < n; i++) {
for (int site : routes[i]) {
for (int j : rec[site]) {
edge[i][j] = edge[j][i] = true;
}
rec[site].push_back(i);
}
}
vector<int> dis(n, -1);
queue<int> que;
for (int bus : rec[source]) {
dis[bus] = 1;
que.push(bus);
}
while (!que.empty()) {
int x = que.front();
que.pop();
for (int y = 0; y < n; y++) {
if (edge[x][y] && dis[y] == -1) {
dis[y] = dis[x] + 1;
que.push(y);
}
}
}
int ret = INT_MAX;
for (int bus : rec[target]) {
if (dis[bus] != -1) {
ret = min(ret, dis[bus]);
}
}
return ret == INT_MAX ? -1 : ret;
}
};
class Solution {
public int shortestBridge(int[][] A) {
int R = A.length, C = A[0].length;
int[][] colors = getComponents(A);
Queue<Node> queue = new LinkedList();
Set<Integer> target = new HashSet();
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c) {
if (colors[r][c] == 1) {
queue.add(new Node(r, c, 0));
} else if (colors[r][c] == 2) {
target.add(r * C + c);
}
}
while (!queue.isEmpty()) {
Node node = queue.poll();
if (target.contains(node.r * C + node.c))
return node.depth - 1;
for (int nei: neighbors(A, node.r, node.c)) {
int nr = nei / C, nc = nei % C;
if (colors[nr][nc] != 1) {
queue.add(new Node(nr, nc, node.depth + 1));
colors[nr][nc] = 1;
}
}
}
throw null;
}
public int[][] getComponents(int[][] A) {
int R = A.length, C = A[0].length;
int[][] colors = new int[R][C];
int t = 0;
for (int r0 = 0; r0 < R; ++r0)
for (int c0 = 0; c0 < C; ++c0)
if (colors[r0][c0] == 0 && A[r0][c0] == 1) {
// Start dfs
Stack<Integer> stack = new Stack();
stack.push(r0 * C + c0);
colors[r0][c0] = ++t;
while (!stack.isEmpty()) {
int node = stack.pop();
int r = node / C, c = node % C;
for (int nei: neighbors(A, r, c)) {
int nr = nei / C, nc = nei % C;
if (A[nr][nc] == 1 && colors[nr][nc] == 0) {
colors[nr][nc] = t;
stack.push(nr * C + nc);
}
}
}
}
return colors;
}
public List<Integer> neighbors(int[][] A, int r, int c) {
int R = A.length, C = A[0].length;
List<Integer> ans = new ArrayList();
if (0 <= r-1) ans.add((r-1) * R + c);
if (0 <= c-1) ans.add(r * R + (c-1));
if (r+1 < R) ans.add((r+1) * R + c);
if (c+1 < C) ans.add(r * R + (c+1));
return ans;
}
}
class Node {
int r, c, depth;
Node(int r, int c, int d) {
this.r = r;
this.c = c;
depth = d;
}
}
作者：LeetCode
链接：https://leetcode.cn/problems/shortest-bridge/solution/zui-duan-de-qiao-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
