Measure the distance of the maze with breadth-first search

Participate in ABC151 and summarize as a review that could not solve D problem

Breadth-first search and depth-first search

Look at the wiki diagram because it's so easy to understand ...

Well, I thought there was a tree like this

Parent A
├ Child AA
│ ├ Grandson AAA
│ └ Grandson AAB
├ Child AB
│ └ Grandson ABA
└ Child AC
├ Grandson ACA
├ Grandson ACB
└ Grandson ACC

Breadth-first search

https://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

Search for all child nodes hanging from the parent node, then search for all grandchild nodes hanging from the searched child node.

Solve using cues

1. Put parent A in the queue (queue status: parent A)
2. Fetch parent A (queue state: empty)
3. Queue all children AA, AB, AC hanging from parent A (queue status: child AA child AB child AC)
4. Take out child AA (queue status: child AB child AC)
5. Queue all grandchildren AAA, AAB hanging from child AA (queue status: child AB child AC grandchild AAA grandchild AAB)
6. Repeat until the queue is empty

The order to search is Parent A → Child AA → Child AB → Child AC → Grandchild AAA → Grandchild AAB → Grandchild ABA → Grandchild ACA → Grandchild ACB → Grandchild ACC

Breadth-first search is to search in the order of parent → child → grandchild

Depth-first search

https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

Go as far as you can go from the parent node, then go back and search for other grandchild nodes.

This is a stack, this is first-in first-out

1. Put parent A on the stack (stack state: parent A)
2. Take out parent A (stack state: empty)
3. Put the children AA, AB, AC hanging on the parent A on the stack (Stack status: Child AA Child AB Child AC)
4. Take out child AC (stack state: child AA child AB)
5. Put the grandchild ACA, ACB, ACC hanging on the child AC on the stack (stack status: child AA child AB grandchild ACB grandchild ACB grandchild ACC)
6. Repeat until the stack is empty

The order to search is Parent A → Child AC → Grandchild ACC → Grandchild ACB → Grandchild ACA → Child AB → Grandchild ABA → Child AA → Grandchild AAA → Grandchild AAB

It's an image of looking at the outer circumference of a tree in order, but it's transmitted ...

I wrote that it uses a stack, but if you search recursively, it becomes a depth-first search (can't you say that in general?)

Unsolved problem

https://atcoder.jp/contests/abc151/tasks/abc151_d

D - Maze Master

Problem statement

Mr. Takahashi has a maze consisting of H × W squares with vertical H squares and horizontal W squares. The cell (i, j) in the i-th row from the top and the j-th column from the left is the wall when Sij is '#' and the road when Sij is '.'. From the road square, you can move to the road squares that are adjacent to each other up, down, left, and right. You cannot move out of the maze, move to a wall square, or move diagonally. Takahashi freely decides the start and goal from the square of the road and hands the maze to Aoki. Aoki moves from the start to the goal with the minimum number of moves. When Takahashi properly positions the start and goal, how many times will Aoki move at the maximum?

Constraint

1≤H,W≤20 Sij is '.' Or '#' S contains two or more '.' You can reach any road square from any road square with 0 or more moves

input

Input is given from standard input in the following format.

H W
S11...S1W
:
SH1...SHW

Answer

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String[] params = in.nextLine().split(" ");
        int h = Integer.parseInt(params[0]);
        int w = Integer.parseInt(params[1]);
        String[][] ss = new String[h][w];
        for (int i = 0; i < h; i++) {
            params = in.nextLine().split("");
            for (int j = 0; j < w; j++) {
                ss[i][j] = params[j];
            }
        }

        //Answer the longest distance starting from all locations
        int maxDistance = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                maxDistance = Math.max( maxDistance , getMaxDistanceWithBfs( ss , i , j ) );
            }
        }

        System.out.println(maxDistance);

    }

    /**
     *Returns the longest distance in breadth-first search
     * @param ss maze array
     * @param startY Y coordinate of start point
     * @param startX X coordinate of start point
     * @return longest distance
     */
    private static int getMaxDistanceWithBfs( String[][] ss , int startY , int startX ) {

        int[][] distances = new int[ss.length][ss[0].length];
        Queue<Integer> queue = new ArrayDeque<>();

        //Definition of distances on all sides Upper left lower right
        int[] dx = { -1 , 0 , 1 , 0 };
        int[] dy = { 0 , 1 , 0 , -1 };

        int maxDistance = 0;

        //Add the start position to the queue
        queue.add( startX );
        queue.add( startY );

        //When the queue is empty=When there are no more places to explore
        //Number of loops=Distance from the start position
        while( !queue.isEmpty()  ) {

            int x = queue.remove();
            int y = queue.remove();

            //If the current location is a wall, do not process
            if( "#".equals( ss[y][x] ) ){
                continue;
            }

            maxDistance = Math.max( maxDistance , distances[y][x] );

            //Check all sides
            for( int i = 0 ; i < 4 ; i++ ){

                //Coordinates of confirmation destination
                int xx = x + dx[i];
                int yy = y + dy[i];

                //The coordinates of the confirmation destination are not outside the array
                if( !( 0 <= yy && yy < ss.length && 0 <= xx && xx < ss[0].length ) ) {
                    continue;
                }

                //The coordinates of the confirmation destination are not walls
                if( !".".equals( ss[yy][xx] ) ) {
                    continue;
                }

                //Not the road you have already taken
                if( distances[yy][xx] != 0 ){
                    continue;
                }

                //Not the starting point
                if( xx == startX && yy == startY ){
                    continue;
                }

                queue.add( xx );
                queue.add( yy );
                distances[yy][xx] = distances[y][x] + 1;

            }

        }

        return maxDistance;

    }

}

Check all directions from the coordinates taken out of the queue, and add it to the queue if it can be passed At that time, store it in a place where you can pass the current distance +1

Because I wrote the judgment array of whether or not it passed together with the array that stores the distance from the starting point I also had to see if the coordinates of the confirmation destination were the starting point

3 5
#####
#..##
#####

In case of such input, answer 1 with S22 as the start point and S23 as the goal point is the correct answer. When you measure the distance from the starting point,

#####
#0.##
#####

#####
#01##
#####

#####
#21##
#####

Like this, the longest route is to go and return after it is judged that the starting point (distance from the starting point: 0) has not passed yet. It seems that there was something similar to the above in the judgment, so when I unchecked it became WA properly

Java has a coordinate class called Point as standard, so maybe I should have used that I didn't need it because I decided to add / remove 2 each in the order of X → Y to the queue.

Remarks

How can I swipe all the coordinates as a starting point?

The problem this time is that the maximum size of the two-dimensional array is 20x20. Even if I checked all the coordinates as the starting point, there was a margin in the execution time. Is it impossible if it gets wider? Would you like to use the same route calculation? Will it be faster than this writing?

I've looked around some of the other people's answers It seems that this problem needs to be swept

It might be better to look at other problems using breadth-first search

1/13 Answer source correction

When I wrote this article, I wrote it like this at first https://atcoder.jp/contests/abc151/submissions/9485696

Points of correction

It's your own

Since we have to prepare an array to measure the distance of each coordinate, System.arraycopy is no longer necessary.

Before correction.java

//Pass a copy as you manipulate the array in the search
for( int k = 0 ; k < h ; k++ ){
    copy[k] = new String[w];
    System.arraycopy( ss[k] , 0 , copy[k] , 0 , w );
}
int distance = getMaxDistanceWithBfs( copy , i , j );

Made to use Math class

It's convenient ...

Before correction.java

int distance = getMaxDistanceWithBfs( copy , i , j );
if (maxDistance < distance) {
    maxDistance = distance;
}

If you decide to put in the queue in the order of X → Y, you do not need a coordinate class

Before correction.java

/**
 *Coordinate class
 */
public static class Position {
    int x;
    int y;
    public Position( int x , int y ) {
        this.x = x;
        this.y = y;
    }
}

Queue<Position> queue = new ArrayDeque<>();
queue.add( new Position( startX , startY ) );

I changed the loop processing

Before correction.java

return distance - 1;

I really hate this book tailing

Originally

1. Loop until the queue is empty
2. Loop to see everything that is the same distance as you took it out
3. Check all sides (why did not use for) Triple loop

By preparing an array to store the distance of each coordinate, the loop of 2 is no longer necessary. Loop 2 was needed to measure the distance, but for some reason it finally needed to be distance-1