ACwing2060-奶牛选美

题目描述

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

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

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

牛皮可用一个 N×MN×M 的字符矩阵来表示，如下所示：

1
2
3
4
5
6
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

其中，XX 表示斑点部分。

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

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

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

在上面的例子中，他只需要给三个 .. 区域内涂色即可（新涂色区域用 ∗ 表示）：

1
2
3
4
5
6
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....

请帮助约翰确定，为了使两个斑点合为一个，他需要涂色区域的最少数量。

输入格式

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

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

输出格式

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

数据范围

1≤N,M≤50

输入样例：

1
2
3
4
5
6
7
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

输出样例：

1
3

笔者解析

1. 统计连通块的位置

我们使用深度优先搜索算法来，逐个统计每个连通块中的每个点的位置

2. 计算连通块的距离

我们使用曼哈顿距离计算法，来找出让两联通块链接的最小路径值，为d(x,y)-1

image.png

笔者代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int N = 100;
    static char[][] arr = new char[N][N];
    static int k = 0,n,m;
    static List<Integer>[] lists = new List[2];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
         n = scanner.nextInt();
         m = scanner.nextInt();

        String s ;
        for (int i = 0; i < n; i++) {
           s  = scanner.next();
            for (int j = 0; j < m; j++) {
                arr[i][j] = s.charAt(j);
            }
        }

        //使用DFS记录下标
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(arr[i][j] == 'X'){
                    lists[k] = new ArrayList<>();
                    DFS(i,j);
                    k++;
                }
            }
        }

        //使用曼哈顿距离法计算
        int min = Integer.MAX_VALUE,dis;
        point p1 = new point();point p2 = new point();
        for (int i = 0; i < lists[0].size(); i++) {
            p1.x = lists[0].get(i)/1000;
            p1.y = lists[0].get(i)%1000;
            for (int j = 0; j < lists[1].size(); j++) {
                p2.x = lists[1].get(j)/1000;
                p2.y = lists[1].get(j)%1000;
                dis = Math.abs(p1.x-p2.x)+Math.abs(p1.y-p2.y)-1;
                min = Math.min(dis,min);
            }
        }
        System.out.println(min);
    }


    //方向向量
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static public void DFS(int x,int y){
       //先将该店设置为已经标记
        arr[x][y] ='.';
        lists[k].add(x*1000+y);
       //向四周遍历
        for (int i = 0; i < 4; i++) {
            int a = dx[i]+x;
            int b = dy[i]+y;
            if(a>=0&&b>=0&&a<n&&b<m&&arr[a][b] =='X'){
                DFS(a,b);
            }
        }
    }
}

class point{
    int x,y;

}