Acwing.2060 奶牛选美(DFS)

题目

听说最近两斑点的奶牛最受欢迎，约翰立即购进了一批两斑点牛。

不幸的是，时尚潮流往往变化很快，当前最受欢迎的牛变成了一斑点牛。

约翰希望通过给每头奶牛涂色，使得它们身上的两个斑点能够合为一个斑点，让它们能够更加时尚。

牛皮可用一个 N×M
的字符矩阵来表示，如下所示：
在这里插入图片描述
其中，X 表示斑点部分。

如果两个 X在垂直或水平方向上相邻（对角相邻不算在内），则它们属于同一个斑点，由此看出上图中恰好有两个斑点。

约翰牛群里所有的牛都有两个斑点。

约翰希望通过使用油漆给奶牛尽可能少的区域内涂色，将两个斑点合为一个。

在上面的例子中，他只需要给三个 .区域内涂色即可（新涂色区域用 ∗表示）：
在这里插入图片描述
请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。

输入格式

第一行包含两个整数 N和 M。

接下来 N行，每行包含一个长度为 M的由 X和 .构成的字符串，用来表示描述牛皮图案的字符矩阵。

输出格式

输出需要涂色区域的最少数量。

数据范围

1≤N,M≤50

输入样例：

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

输出样例：

题解

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 *
 * @author akuya
 * @create 2024-03-18-21:28
 */
public class Main {

    static int N=55;
    static char a[][]=new char[N][N];
    static int n,m;
    static int xy[][]={{1,0,-1,0},{0,1,0,-1}};
    static List<sit> list=new ArrayList<>();
    static List<sit> list2=new ArrayList<>();
    static int ans=Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        m=scanner.nextInt();
        for(int i=1;i<=n;i++){
            String t=scanner.next();
            for(int j=0;j<t.length();j++){
                a[i][j+1]=t.charAt(j);
            }
        }

        int flag=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i][j]=='X'){
                    if(flag==0) {
                        dfs(i, j, list);
                        flag++;
                    }
                    else
                        dfs(i,j,list2);
                }
            }
        }

        for(sit s1:list){
            for(sit s2:list2){
                ans=Math.min(ans,Math.abs(s1.x-s2.x)+Math.abs(s1.y-s2.y));
            }
        }

        System.out.println(ans-1);
    }

    public static void dfs(int i,int j,List<sit> list){
        list.add(new sit(i,j));
        a[i][j]='.';
        for(int k=0;k<4;k++){
            int x=j+xy[0][k];
            int y=i+xy[1][k];
            if(x<=m&&x>=1&&y<=n&&y>=1&&a[y][x]=='X'){
                dfs(y,x,list);
            }
        }


    }
}

class sit{
    int x;
    int y;

    public sit(int x, int y) {
        this.x = x;
        this.y = y;
    }
}