Key and room

Knowledge: figure; Recursion; BFS

Topic describes

There are N rooms, and you start out in room 0. Each room has a different number: 0,1,2… N-1, and there may be some keys in the room that allow you to enter the next room.

Formally, there is a key list rooms[I] for each room I, and each key room [I][j] is represented by an integer in [0,1,…, n-1], where N = rooms.length. Key rooms[I][j] = v

Initially, all rooms except room 0 were locked.

You can move freely from room to room.

Return true if you can enter each room, false otherwise.

The sample
Input: [[1],[2],[3],[] Output: true Explanation: We start with room 0 and get key 1. Then we go to room one and get key two. Then we go to room two and get key three. Finally we went to room 3. Since we were able to enter every room, we return true. Input: [[1, 3], [3, 1], [2], [0]] output: false interpretation: we can't enter the room number 2.Copy the code

Solution 1: Breadth First (BFS)

Breadth first means we don’t get a key to the end of the room, we go room by room, get the key to the first room, open all the doors corresponding to the key in the first room, then go to the second room. One by one.

class Solution { public boolean canVisitAllRooms(List<List<Integer>> rooms) { int n = rooms.size(); boolean[] vis = new boolean[n]; // The flag bit is to prevent repeated traversal; int num = 0; Queue<Integer> queue = new LinkedList<>(); vis[0] = true; To prevent the node from joining the queue for many times, set it to visited before joining the queue. queue.add(0); // Room 0 is ready; while(! queue.isEmpty()){ int x = queue.poll(); num++; for(int i : rooms.get(x)){ if(! Vis [I]){// Not accessed; vis[i] = true; queue.add(i); // Ensure that the queue is not traversed; } } } return n == num; }}Copy the code

experience

  • 1. As long as it’s breadth-first, definitely use queues, which are naturally together. One side pop-up, while traversing, after a pop-up, put its children or its association into the team, to ensure that this layer, or this node are pop-up, and then continue to play the next layer or the next node.

  • 2. Tree BFS: Queue root nodes first and then iterate layer by layer. The BFS of a graph is the same, with the difference from the BFS of a tree:

    • 1. A tree has only one root, and a graph can have multiple source points, so you need to queue multiple source points first.
    • 2. Trees are directed, so there is no need for the flag to be visited, but for undirected graphs, the flag must be visited! In addition, to prevent a node from joining the queue for several times, you need to set it as visited before joining the queue!

  • 3. Trees use MORE DFS and graphs use more BFS;

133. Cloning figure

Knowledge: figure; Recursion; BFS

Topic describes

Given a reference to a node in an undirected connected graph, return a deep copy (clone) of the graph.

Each Node in the diagram contains its value val (int) and a list of its neighbors (list[Node]).

class Node {
    public int val;
    public List<Node> neighbors;
}
Copy the code
The sample

Input: adjList = [[2, 4], [1, 3], [2, 4], [1, 3]] output: [[2, 4], [1, 3], [2, 4], [1, 3]] : there are four nodes in figure. Node 1 has the value 1 and has two neighbors: nodes 2 and 4. Node 2 has the value 2 and has two neighbors: node 1 and node 3. Node 3 has the value 3 and has two neighbors: node 2 and node 4. Node 4 has the value 4 and has two neighbors: node 1 and node 3. Input: adjList = [[]] Output: [[]] Explanation: The input contains an empty list. The graph has only one node with a value of 1, and it has no neighbors. Input: adjList = [] Output: [] Explanation: This graph is empty, it does not contain any nodes. Input: adjList = [[2],[1] output: [[2],[1]]Copy the code

Solution 1: Breadth First (BFS)

As with depth, you need to have a map to determine if it is traversed. Using BFS, create a queue and queue each node in turn. Join the head node, and then take it out, iterate over the neighbor node of the team, if not visited, join the team, clone and add it to the map, if visited, update the neighbor node of the clone node.

// Definition for a Node. class Node { public int val; public List<Node> neighbors; public Node() { val = 0; neighbors = new ArrayList<Node>(); } public Node(int _val) { val = _val; neighbors = new ArrayList<Node>(); } public Node(int _val, ArrayList<Node> _neighbors) { val = _val; neighbors = _neighbors; } } class Solution { public Node cloneGraph(Node node) { Map<Node, Node> vis = new HashMap<>(); if(node == null) return null; Queue<Node> queue = new LinkedList<>(); queue.add(node); // the first node joins the queue; vis.put(node, new Node(node.val, new ArrayList())); // clone node joins table; while(! queue.isEmpty()){ Node head = queue.poll(); for(Node neighbor : head.neighbors){ if(! vis.containsKey(neighbor)){ vis.put(neighbor, new Node(neighbor.val, new ArrayList())); queue.add(neighbor); // Set access to merge queue in sequence; } vis.get(head).neighbors.add(vis.get(neighbor)); // Add neighbor, note is added clone; } } return vis.get(node); }}Copy the code

1162. Map analysis

Knowledge: figure; recursive

Topic describes

You now have a grid of size N x N, with each cell marked with zeros and ones. Where 0 represents the ocean and 1 represents the land. Please find an ocean cell that has the maximum distance from the nearest land cell.

We here said the Distance is the “Manhattan Distance” (Manhattan short) : (x0, y0) and (x1, y1) is the Distance between the two cell | x0 – x1 + | | y0 – y1 |.

If only land or sea is on the grid, return to -1.

The sample

Input: [[1,0,1],[0,0,0],[1,0,1] output: 2 explanation: the maximum distance between oceanic cells (1, 1) and all terrestrial cells is 2.Copy the code

Input: [[1,0,0],[0,0,0]] output: 4 explanation: the maximum distance between oceanic cells (2, 2) and all terrestrial cells is 4.Copy the code

Solution 1: Breadth First (BFS)

Tree BFS: queue root nodes first and then iterate layer by layer. The BFS of a graph is the same, with the difference from the BFS of a tree: 1. A tree has only one root, while a graph can have multiple source points, so it needs to queue multiple source points first. 2. Trees are directed, so there is no need for the flag to be visited, but for undirected graphs, the flag must be visited! In addition, to prevent a node from joining the queue for several times, you need to set it as visited before joining the queue!

Tree breadth-first search: from root to child nodes; For breadth first of one source and breadth first of multiple sources, see the link below for breadth First search

So this is a sample of a multi-source breadth-first search, where we look for the ocean cell that’s farthest from land, and we can translate that into starting with all of the land and going out and going out, and then going out to the farthest. The first round of changes took each land as a starting point, and the sea within walking distance; The second round of changes is based on the first round of walking two blocks to reach the sea, this way constantly changing, the farther the uncovered sea is from the land, the closer to the sea we want to find, until the map is completely covered.

Public int maxDistance(int[][] grid) {class Solution {public int maxDistance(int[][] grid) { int[] dx = {0, 0, 1, -1}; int[] dy = {1, -1, 0, 0}; // Set four change directions; Queue<int[]> queue = new LinkedList<>(); int m = grid.length, n = grid[0].length; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(grid[i][j] == 1){ queue.add(new int[]{i, j}); } } } if(queue.size() == 0 || queue.size() == m*n) return -1; // There is no land or sea; // It expands outward round and round from land to land, the last being the farthest; int[] point = null; // queue exit point; while(! queue.isEmpty()){ point = queue.poll(); // Find four adjacent coordinates of this coordinate; int x = point[0], y = point[1]; for(int i = 0; i < 4; i++){ int newX = x + dx[i]; int newY = y + dy[i]; if(newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] ! = 0){ continue; // Discard invalid coordinates and surrounding land; } grid[newX][newY] = grid[x][y]+1; // expand outward; queue.add(new int[]{newX, newY}); } } return grid[point[0]][point[1]]-1; // Return the coordinates of the last queue; }}Copy the code

Method 2:

  • grid(r, c)The four adjacent grids of are:(r-1, c),(r+1, c),(r, c-1) 和 (r, c+1);
  • Using the functioninAreaJudge whether the coordinate of the current grid is within the grid range;
  • Mark the traversed grid as 2 to avoid repeated traversal.

For the nature of the grid structure, grid structure of DFS traversal technique is not very understanding of students, can brush up on my previous article: LeetCode examples: | 12 islands: DFS of grid structure.

DFS traversal of grid structures was covered in the previous article, and this article is a good introduction to BFS traversal of grid structures. To solve the shortest path problem, we first need to write the sequence traversal code, similar to the binary tree sequence traversal code above, can write the grid sequence traversal code:

Void BFS (int[], int I, int j) {Queue<int[]> Queue = new ArrayDeque<>(); void BFS (int[], int I, int j) {Queue<int[]> Queue = new ArrayDeque<>(); queue.add(new int[]{r, c}); while (! queue.isEmpty()) { int n = queue.size(); for (int i = 0; i < n; i++) { int[] node = queue.poll(); int r = node[0]; int c = node[1]; if (r-1 >= 0 && grid[r-1][c] == 0) { grid[r-1][c] = 2; queue.add(new int[]{r-1, c}); } if (r+1 < N && grid[r+1][c] == 0) { grid[r+1][c] = 2; queue.add(new int[]{r+1, c}); } if (c-1 >= 0 && grid[r][c-1] == 0) { grid[r][c-1] = 2; queue.add(new int[]{r, c-1}); } if (c+1 < N && grid[r][c+1] == 0) { grid[r][c+1] = 2; queue.add(new int[]{r, c+1}); }}}}Copy the code

The sequence traversal code above has a few points to note:

  • The element type in the queue isint[]Arrays, each of length 2, containing the row and column coordinates of the cell.
  • To avoid repeated traversal, the same technique used for DFS traversal is used: the traversal cells are marked as 2. Note: We mark the grid as 2 before putting it in the queue. Think about it. Why?
  • Check that the grid coordinates are within the grid range before you queue a cell to avoid queuing “nonexistent” cells.

The grid traversal code still has some areas that can be optimized. Since a grid has four adjacent grids, the code judges the validity of grid coordinates four times, the code is slightly wordy. We can use a Moves array to store the four directions of an adjacent grid:

int[][] moves = {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1},
};
Copy the code

Then turn the four if judgments into a loop:

for (int[][] move : moves) { int r2 = r + move[0]; int c2 = c + move[1]; if (inArea(grid, r2, c2) && grid[r2][c2] == 0) { grid[r2][c2] = 2; queue.add(new int[]{r2, c2}); }}Copy the code

Now that we’ve written the code for sequential traversal, let’s look at how to solve the shortest path problem in this case.

This problem is looking for the ocean grid farthest from land. Assuming there is only one land cell in the grid, we can start from this land cell and do a sequence traversal until all the cells have been traversed. And finally, how many layers are traversed, the farthest distance of the ocean grid is.

Distance from a single land grid (GIF)

So what happens when you have multiple land grids? One method is to do a sequence traversal for each land grid as a starting point, but such time is too expensive.

BFS can start with more than one grid at a time. We can put all the land cells into the initial queue at the same time, and then start the sequence traversal. The result of such traversal is shown in the figure below:

Distance from multiple land grids

This traversal method is actually called “multi-source BFS.” The definition of multi-source BFS is not the focus of today’s discussion, just remember that multi-source BFS are very convenient and you only need to put multiple source points into the initial queue at the same time.

It should be noted that although the diagram above uses 1, 2, 3 and 4 to represent the number of layers traversed by the sequence, in the code, we do not need to mark the number of layers traversed by each cell. We only need to record the number of layers currently traversed (i.e. the distance to the land cell) with a distance variable.

Finally, the solution code is as follows:

public int maxDistance(int[][] grid) {
  int N = grid.length;

  Queue<int[]> queue = new ArrayDeque<>();
  *// Queue all land grids *
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (grid[i][j] == 1) {
        queue.add(new int[]{i, j}); }}} *// If only land or sea is on the map, return -1*
  if (queue.isEmpty() || queue.size() == N * N) {
    return -1;
  }

  int[][] moves = {
    {-1.0}, {1.0}, {0, -1}, {0.1}};int distance = -1; *// Record the number of layers currently traversed (distance) *
  while(! queue.isEmpty()) { distance++;int n = queue.size();
    for (int i = 0; i < n; i++) { 
      int[] node = queue.poll();
      int r = node[0];
      int c = node[1];
      for (int[] move : moves) {
        int r2 = r + move[0];
        int c2 = c + move[1];
        if (inArea(grid, r2, c2) && grid[r2][c2] == 0) {
          grid[r2][c2] = 2;
          queue.add(new int[]{r2, c2}); }}}}return distance;
}

*// Check whether coordinates (r, c) are in the grid *
boolean inArea(int[][] grid, int r, int c) {
  return 0 <= r && r < grid.length 
    && 0 <= c && c < grid[0].length;
}
Copy the code

experience

Tree BFS: queue root nodes first and then iterate layer by layer. The BFS of a graph is the same, with the difference from the BFS of a tree: 1. A tree has only one root, while a graph can have multiple source points, so it needs to queue multiple source points first. 2. Trees are directed, so there is no need for the flag to be visited, but for undirected graphs, the flag must be visited! In addition, to prevent a node from joining the queue for several times, you need to set it as visited before joining the queue!

Open the turntable lock

Knowledge: figure; BFS

Topic describes

You have a turntable lock with four round paddles. Each dial wheel has 10 Numbers: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. Each dial wheel can rotate freely: for example, ‘9’ becomes ‘0’ and ‘0’ becomes ‘9’. Each rotation can only rotate one digit of one dial wheel.

The initial lock number is ‘0000’, a string representing the numbers of the four dial wheels.

The list deadends contains a set of death numbers. Once the number of the dial wheel matches any element in the list, the lock is permanently locked and cannot be rotated.

The string target represents the number that can be unlocked. You need to give the minimum number of rotations required to unlock it. If you can’t unlock it anyway, return -1.

The sample
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202" Could move the sequence of "0000" - > "1000" - > "1100" - > "1200" - > "1201" - > "1202" - > "0202". Note that sequences such as "0000" -> "0001" -> "0002" -> "0102" -> "0202" cannot be unlocked because the lock will be locked when "0102" is tapped. Deadends = ["8888"], target = "0009" Output: 1 Input: Deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888" Output: -1 Description: Cannot rotate to target number and is not locked. Input: deadends = ["0000"], target = "8888Copy the code

Solution 1: BFS

This problem looks around, in fact, through the scene to see the nature, is actually a picture, what do you mean, each code can be seen as a figure of nodes, the goal is to find the target node, how to do, traverse the bai, what time to find what time stop, and graph traversal natural to use BFS, actually have eight adjacent nodes, each node Because when it turns, the next possible password is eight, for example, “0000”, when it turns, “1000,9000,0100,0900…” , this is the adjacent node; Then, a visited is used to record the ones that have been traversed, so as to avoid going back. In addition, if there is a password equal to deadend, it is unnecessary to skip this password.

BFS algorithm framework:

Int BDS(Node start, Node target){Queue<Node> Queue; // Core structure: queue; Set<Node> visited; // It is used in both diagrams because there is crossover and it will go backwards, but not in trees because there is a next pointer; queue.offer(start); // Start to join the queue; visited.add(start); int step = 0; // Record the number of diffusion steps; while(queue.isEmpty()){ int size = queue.size(); // From all nodes in the current queue to nodes associated with it; for(int i = 0; i < size; i++){ Node cur = queue.poll(); if(cur == target){ return step; // Check whether you have reached the end; } for(Node x: cur.adj()){// This is the neighbor of the current Node; if(! Contains (x)){// It contains(x); Never go back; queue.offer(x); visited.add(x); } } } step++; // Note that the step count is updated here; }}Copy the code

Answer key:

class Solution { public int openLock(String[] deadends, String target) { Set<String> dead = new HashSet<>(); for(String s:deadends){ dead.add(s); } Queue<String> queue = new LinkedList<>(); queue.offer("0000"); Set<String> visited = new HashSet<>(); visited.add("0000"); // Record all passwords that have been traversed; int step = 0; while(! queue.isEmpty()){ int size = queue.size(); for(int i = 0; i < size; i++){ String cur = queue.poll(); // Cutoff condition; if(dead.contains(cur)) continue; if(cur.equals(target)) return step; // Handle adjacent nodes; Eight in all; for(int j = 0; j < 4; j++){ String up = plusOne(cur, j); if(! visited.contains(up)){ visited.add(up); queue.offer(up); } String down = minusOne(cur, j); if(! visited.contains(down)){ visited.add(down); queue.offer(down); } } } step++; } return -1; } private String plusOne(String s, int j){ char[] ch = s.toCharArray(); if(ch[j] == '9') ch[j] = '0'; else ch[j] += 1; return new String(ch); } private String minusOne(String s, int j){ char[] ch = s.toCharArray(); if(ch[j] == '0') ch[j] = '9'; else ch[j] -= 1; return new String(ch); }}Copy the code

Take a closer look at the above solution, basically is the same as the framework is the template, pay attention to flexibility.

Original author: Curryxin

Link: www.cnblogs.com/Curryxin/p/…

Reference links: (LeetCode examples: | 13 BFS usage scenarios: sequence traversal, the shortest path problem (qq.com))