Oilfield exploration problems

One   Original link

Oil Deposits - UVA 572 - Virtual Judgehttps://vjudge.net/problem/UVA-572

Two   Input and output

1  Input

The input file contains one or more rectangular regions . The second in each region 1 Each row has two integers  m  and  n, Indicates the number of rows and columns in the region . If  m=0, Indicates the end of input ; Otherwise, there will be  m  That's ok , Every line has  n  Characters . Each character corresponds to a square area , character *  Indicates no oil , character @  It means there is oil .

2  Output

For each rectangular region , Each row outputs the number of reservoirs .

3  sample input

1 1

*

3 5

*@*@*

**@**

*@*@*

1 8

@@****@*

5 5

****@

*@@*@

*@**@

@@@*@

@@**@

0 0

4  sample output

0

1

2

2

3、 ... and   Algorithm analysis

To traverse such oil fields , From each @  Grid departure , Look for all around it @  lattice , At the same time, these grids are marked with a connected component number , Finally, the number of connected components is output . Use the depth first search of the graph .

for example , For the following use case

5 5

****@

*@@*@

*@**@

@@@*@

@@**@

0 0

The number of reservoirs is the number of connected components , As shown in the figure below .

According to the problem description , level 、 Both vertical and diagonal lines are considered adjacent , So when searching , It can be downloaded from 8  Depth first search in four directions , As shown in the figure below .

Four   Algorithm design

1  Judge each position in the character matrix , If the connected component number is not marked and is @, Then the depth first search is performed from this position .

2  When searching for elements, you need to judge whether they are out of bounds , Whether there is a connected component number or not @, Otherwise, mark the position as the connected component  id, From this position , Along the 8  Continue depth first search in all directions .

3  Because it may contain multiple connected components , So you need to start from each unmarked @  Depth first search .

5、 ... and   Code

package graph;

import java.util.Scanner;

public class UVA572 {
    static int maxn = 100 + 5;
    static String str[] = new String[maxn]; //  Store character matrix 
    static int m; //  That's ok 
    static int n; //  Column 

    static int setid[][];

    /**
     *  Function description ： Depth-first search 
     *
     * @param x   That's ok 
     * @param y   Column 
     * @param id  Connected component number 
     * @author cakin
     * @date 2022/6/26
     */
    static void dfs(int x, int y, int id) {
        //  out 
        if (x < 0 || x >= m || y < 0 || y >= n) {
            return;
        }
        //  There are connected component numbers or not '@'
        if (setid[x][y] > 0 || str[x].charAt(y) != '@') {
            return;
        }
        setid[x][y] = id;
        for (int dx = -1; dx <= 1; dx++)
            for (int dy = -1; dy <= 1; dy++) {
                if (dx != 0 || dy != 0)
                    //  Search deeply in eight directions 
                    dfs(x + dx, y + dy, id);
            }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            m = scanner.nextInt();
            n = scanner.nextInt();
            if (m == 0 && n == 0) {
                return;
            }
            for (int i = 0; i <= m - 1; i++) {
                str[i] = scanner.next();
            }
            //  Initialize connected components 
            setid = new int[maxn][maxn];
            int cnt = 0;
            for (int i = 0; i <= m - 1; i++) {
                for (int j = 0; j <= n - 1; j++) {
                    if (setid[i][j] == 0 && str[i].charAt(j) == '@')
                        dfs(i, j, ++cnt);
                }
            }
            System.out.println(cnt);
        }
    }
}

6、 ... and   test