This is a series of articles that I have compiled in my study and memo. The third. This is a continuation of this article. Introduction to algorithms in java-Search (depth-first search) In this article

--Breadth-first search

I will study about.

It's also called BFS (breadth-first search). (Breadth: width) I will write this while studying. For the difference from the depth-first search that looks like a tree, see this article "Introduction to algorithms with java-Search (depth-first search)" Please give me.

It seems to be effective for problems such as finding the shortest path of a maze.

It seems to use a data structure called a queue as an implementation method. In depth-first search, "first in, last out" stack, Keep in mind that breadth-first search uses a "first in, first out" queue.

Also, depth-first search could be implemented by recursion, but it seems that it is impossible or difficult to process in the order of queues if it is recursion. Do you use queue? .. I don't want to remember new libraries or types at the beginning of my studies. .. .. I don't feel like I can use it right away. ..

By the way, stacks and cues will appear in the Fundamental Information Technology Engineer Examination, so I think it's okay, but I don't know! For those who say, this article "Extreme stacks and cues! ~ Special feature on ideas and uses ~" seems to be easy to understand, so study it. Let's do it.

For the time being, the example is easy to understand Last time I thought I'd try arc031-b implemented in DFS, but it may not fit BFS. So I will try another example.

Example: AtCoder --agc033-a "Darker and Darker"

* Please refer to the problem link as much as possible

(Section start) 【Problem statement】 It is given black and white squares with H rows vertically and W columns horizontally. The state of the square is represented by HW characters from A11 to AHW. When the square in the i-th row from the top and the j-th column from the left is black, Aij is #, the i-th row from the top, and j from the left. Aij is. When the squares in the row are white.

Repeat the following steps until all the cells are black. All white cells that share one side and have one or more black cells among adjacent cells become black. Find out how many operations you will be performing. However, there is at least one black cell in the first cell given.

[Restrictions] 1≦H,W≦1000 Aij is # or .. There is at least one black square in the given square.

【input】 Input is given from standard input in the following format.

```
H W
A11 A12 ... A1W
:
AH1 AH2 ... AHW
```

【output】 Output the number of operations performed.

(End of section)

[Answer example]

` main.java`

```
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// height
int h = sc.nextInt();
// width
int w = sc.nextInt();
//State of squares
char[][] masu = new char[h][w];
//Prepare BFS Queue
Deque<XY> q = new ArrayDeque<>();
//Receive input& '#'EnQueue
for (int i = 0; i < h; i++) {
masu[i] = sc.next().toCharArray();
for (int j = 0; j < w; j++) {
if ('#' == masu[i][j]) {
q.add(new XY(i, j, 0));
}
}
}
// ans
int max_depth = 0;
//BFS main processing
for (;;) {
//Infinite loop start
//Exit conditions
if (q.size() < 1) {
break;
}
//queue to dequeue
//poll method fetches from queue&Remove from queue
XY xy = q.poll();
int x = xy.x;
int y = xy.y;
int depth = xy.depth;
//Record the number of operations
if (depth >= max_depth) {
max_depth = depth;
}
//Make the area around the current position black
if (x + 1 < w && masu[y][x + 1] == '.') {
//Right square
masu[y][x + 1] = '#';
q.add(new XY(y, x + 1, depth + 1));
}
if (x - 1 >= 0 && masu[y][x - 1] == '.') {
//Left square
masu[y][x - 1] = '#';
q.add(new XY(y, x - 1, depth + 1));
}
if (y + 1 < h && masu[y + 1][x] == '.') {
//Lower square
masu[y + 1][x] = '#';
q.add(new XY(y + 1, x, depth + 1));
}
if (y - 1 >= 0 && masu[y - 1][x] == '.') {
//Upper square
masu[y - 1][x] = '#';
q.add(new XY(y - 1, x, depth + 1));
}
}
System.out.println(max_depth);
}
}
class XY {
int y;
int x;
int depth;
XY(int y, int x, int d) {
this.x = x;
this.y = y;
depth = d;
}
}
```

It is like this. The policy is as follows.

--In the initial state, put the information of the black square in the Queue. (Coordinates, how many times it turned black (= depth)) --Get information from the Queue and search for the squares on the top, bottom, left, and right of that coordinate. If it is white, make it black, increment the depth, and store it in the Queue. If it's black, I don't do anything. --Repeat until there is no data in the Queue (≒ all black).

In this order, the depths are always 0, 1, 2 ... and they enter the Queue in order, so the depth when it turns black is the minimum depth of that square, so once it turns black, it's OK. I am grateful for that.

By the way, is this a variant of breadth-first search, or is it classified as a type of BFS with multiple starting points? It seems to be done.

I learned how to use Queue rather than breadth-first search. Lol I think Deque's poll method is often used, so I definitely want to remember it.

I'd like to visually see the movement when implementing breadth-first search this time as well, but since I learned from the previous article (I thought you could understand it, w) I will stop. ** I have written comments in the code in an easy-to-understand manner, so please follow them. ** **

If this is written for the time being, it seems that the application will work. The rest is a problem exercise. After learning the theory, practice it repeatedly and settle in yourself. I want to keep up with the numbers.

That's all for this time. Next time, I will touch on bit full search. looking forward to!

Recommended Posts