Introduction:
Among algorithms and data structures, BFS (Breadth First Search) is a commonly used graph search algorithm. It traverses the nodes of the graph layer by layer to find the target node or determine the shortest path. However, when solving BFS-type problems, we often encounter situations where we need to determine the neighbors of a node and process them accordingly. At this time, using the adjacent point offset array can provide a simple and efficient solution.
Text:
1. Breadth-first search algorithm and its application scenarios:
Breadth-first search algorithm (BFS) is a queue-based traversal algorithm commonly used in process analysis, maze games and other fields. It traverses the nodes of the graph layer by layer to find the target node or determine the shortest path, and has a wide range of application prospects.
In BFS, we start with an initial node, add it to the queue, then iterate through all the neighbor nodes of that node and add them to the queue as well, until the queue is empty. The neighbor nodes traversed here refer to the nodes directly connected to the current node. During the traversal process, we need to record the status of each node to avoid repeated visits and infinite loops. At the same time, we also need to record path information in order to find the shortest path.
2. The concept and function of adjacent point offset array:
The neighbor offset array is a data structure used to represent the neighbor relationship of nodes. For example, in a two-dimensional matrix, the coordinates of a node are (x, y), then the coordinates of its four neighbor nodes above, below, left and right can be expressed as:
Up: (x-1,y)
Left: (x,y-1) Right: (x,y + 1)
Lower: (x + 1,y)
For the four neighbors above, we can define an adjacent point offset array offset, where offset[0] = [-1,0] represents the offset of the upper neighbor, and offset[1] = [1,0] represents the offset of the neighbor below, and so on. Then we can calculate the neighbor coordinates of node (x,y) as follows:
int[][] offset = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; // Adjacent point offset array
int x = currentNode.getX(); // x coordinate of the current node
int y = currentNode.getY(); // The y coordinate of the current node
for (int i = 0; i < 4; i + + ) {
int nx = x + offset[i][0]; // Calculate the x coordinate of neighbor nodes
int ny = y + offset[i][1]; // Calculate the y coordinate of neighbor nodes
// Here you can perform corresponding operations based on the coordinates of neighbor nodes
}
Example question: AcWingSnake Matrix
Input two integers n and m, output a matrix with n rows and m columns, and fill the matrix with numbers 1 to n×m in a serpentine shape.
Please refer to the example for the specific matrix form.
Input format
The input is one line, containing two integers n and m.Output format
Output a matrix that meets the requirements.The matrix occupies n rows, and each row contains m space-separated integers.
data range
1≤n,m≤100
Input example:
3 3
Output sample:
1 2 3
8 9 4
7 6 5
Code:
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] res = new int[n][m];
//Create offset
int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
// current location
int x = 0, y = 0, d = 1;
for (int i = 1; i <= n * m; + + i) {
res[x][y] = i;
// a, b are the upper, right, lower and left positions
int a = x + dx[d], b = y + dy[d];
if (a < 0 || a >= n || b < 0 || b >= m || res[a][b] > 0) {
d = (d + 1) % 4;
a = x + dx[d];
b = y + dy[d];
}
x = a;
y = b;
}
for (int i = 0; i < n; + + i) {
for (int j = 0; j < m; + + j) {
System.out.print(res[i][j] + " ");
}
System.out.println();
}
}
}
operation result:
In this question, offset arrays dx and dy are defined, which are used to calculate the coordinates of neighbor nodes. The offset (dx[i], dy[i]) of the i-th position in the array represents the coordinate change when moving one step left, down, right, and up respectively.
You then use a loop to iterate through each number from 1 to n×m, filling the current number i into the current position (x, y) of the matrix, and updating the values of x and y.
Then, to determine if it “hit the wall”, you calculate the next position (a, b). If (a, b) exceeds the matrix boundary or has been filled, the direction needs to be changed. At this point, youincrement the direction d by 1 modulo 4 and recalculate the value of (a, b).
Finally, iterate over and print each element in the matrix. In this way, a matrix filled in a snake shape is obtained.
3. Analyze the time complexity and space complexity of the algorithm, as well as its advantages and disadvantages.
The time complexity is O(n * m), where n represents the number of rows of the matrix and m represents the number of columns of the matrix. Mainly because we need to loop through the entire matrix to fill in the numbers.
The space complexity is O(n * m) because we need to create a two-dimensional array of size n rows and m columns to represent the final matrix.
advantage:
- Simple and intuitive: This algorithm uses a simulation method to generate a serpentine matrix by traversing the filled numbers one by one, which is easy to understand and implement.
- Low time complexity: The time complexity of the algorithm is linear and proportional to the size of the matrix, so it is more efficient in most cases.
shortcoming:
- Large space occupation: In order to store the matrix, an additional two-dimensional array of n rows and m columns needs to be created. When the matrix is larger, it will occupy more memory space.
- Not universal: This algorithm is only applicable to the specific problem of filling matrices in a serpentine shape, and is not applicable to other types of matrix filling problems.
Example question: Looking at a question similar to AcWing Horse Racing Day Question / Mobile Knight
Can only move in a 2*3 diagonal
Given an n?n chessboard, and a start position and end position.
The horizontal and vertical coordinates of the chessboard range from 0 to n?1.
Place a chess knight at the starting position. How many steps does it take to move it to the end position?
Possible moves for a knight on the chessboard are as follows:
Input format
The first line contains an integer T, indicating that there are T sets of test data.
The first line of each set of test data contains an integer n, indicating the size of the chessboard.
The second line contains two integers x,y used to represent the knight’s starting position coordinates (x,y).
The third line contains two integers x, y used to represent the knight’s end position coordinates (x, y).
Output format
Each set of data outputs an integer, indicating the minimum number of steps the knight needs to move. Each result occupies one line.
data range
4 ≤ n ≤ 300,
0 ≤ x, y ≤ n?1Input example:
3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1Output sample:
5 28 0
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static class Pair{
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static int[] dx = new int[]{-2, -1, 1, 2, 2, 1, -1, -2};
static int[] dy = new int[]{1, 2, 2, 1, -1, -2, -2, -1};
public static void main(String[] args) {
Scanner sca = new Scanner(System.in);
int T = sca.nextInt();
while (T -- > 0) {
int n = sca.nextInt();
int sx = sca.nextInt();
int sy = sca.nextInt();
int ex = sca.nextInt();
int ey = sca.nextInt();
int ans = dfs(n, sx, sy, ex, ey);
System.out.println(ans);
}
}
public static int bfs(int n, int sx,int sy, int ex, int ey) {
int[][] dist = new int[n][n];
for (int i = 0; i < n; + + i) {
Arrays.fill(dist[i], -1);
}
Queue<Pair> queue = new LinkedList<>();
queue.offer(new Pair(sx,sy));
dist[sx][sy] = 0;
while (!queue.isEmpty()) {
Pair cur = queue.poll();
int x = cur.x;
int y = cur.y;
if (x == ex & amp; & y ==ey) {
return dist[x][y];
}
for (int i = 0; i < 8; + + i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 & amp; & amp; nx < n & amp; & amp; ny >= 0 & amp; & amp; ny < n & amp; & amp; dist[nx][ny] == - 1) {
queue.offer(new Pair(nx,ny));
dist[nx][ny] = dist[x][y] + 1;
}
}
}
return -1;
}
}
The Pair class is defined here to facilitate storing the coordinates of the location (x, y) and storing it in the queue as a queue element. Using a custom Pair class can represent the location more intuitively and can be stored and transferred conveniently.
This approach is to increase the readability and maintainability of the code. If you directly use arrays or other methods to store position coordinates, it may make the code difficult to understand and maintain. By defining the Pair class, you can clearly express that each element represents a coordinate point, improving the readability of the code.
For bfs core functions:
The core function of searching the shortest path using the BFS algorithm.
First, create a two-dimensional array dist to record the shortest number of steps at each position. When initializing, set the step count of all locations to -1, indicating that they have not been visited yet.
Then, create a queue to store the location to be searched. Add the starting position (sx, sy) to the queue and set its step number dist[sx][sy] to 0, indicating that the starting position has been visited and the number of steps is 0.
Enter a loop until the queue is empty. In each loop, the current position (x, y) is taken from the queue. Check whether the current position is the end position (ex, ey). If so, it means the shortest path has been found and directly returns dist[x][y], which is the number of steps of the current position.
Traverse all neighbor nodes of the current position, and by calculating the combination of the current position (x, y) and the dx and dy arrays, the coordinates (nx, ny) of the neighbor node can be obtained.
If the neighbor node (nx, ny) is within the legal range and has not been visited yet (i.e. dist[nx][ny] == -1), add it to the queue and update its step number to dist[x][y ] + 1, indicating the number of steps from the starting point to the neighbor node. Through such operations, feasible neighbor nodes are continuously expanded and their step numbers are updated so that the shortest path can be obtained in subsequent searches.
When the queue is empty, it means that the end position cannot be reached, and -1 is returned, indicating that there is no shortest path.
Summary:
Using an array of adjacent point offsets to solve BFS-type problems can greatly simplify the code and improve the readability and maintainability of the algorithm. It standardizes the neighbor determination and processing process of nodes, and is suitable for various scenarios that require neighbor operations. When solving BFS problems, the adjacent point offset array is a powerful tool that is worth learning and mastering in depth.