AcWing 2060. 奶牛选美
原题链接
中等
作者:
忆南cc
,
2024-03-29 21:59:37
,
所有人可见
,
阅读 12
题目描述
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
//用于存储第一个点的所有位置坐标
public static ArrayList<int[]> map1 = new ArrayList<int[]>();
//用于存储第二个点的所有位置坐标
public static ArrayList<int[]> map2 = new ArrayList<int[]>();
public static char[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] s = in.readLine().split(" ");
//n * m矩阵
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
arr = new char[n][m];
for(int i = 0;i < n;i++) {
String[] s1 = in.readLine().split("");
for(int j = 0;j < m;j++) {
arr[i][j] = s1[j].charAt(0);
}
}
int k = 1;
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
if(arr[i][j] == 'X') {
dfs(i,j,k++);
}
}
}
map1.sort((a,b) -> a[0] - b[0]);
map2.sort((a,b) -> a[0] - b[0]);
int min = Integer.MAX_VALUE;
for(int i = 0;i < map1.size();i++) {
for(int j = 0;j < map2.size();j++) {
//曼哈顿距离计算公式求最少填数,-1是因为只要求两个点之间的数,不需要到对面那个点
min = Math.min(Math.abs(map1.get(i)[0] - map2.get(j)[0]) +
Math.abs(map1.get(i)[1] - map2.get(j)[1]) - 1, min);
}
}
System.out.println(min);
}
public static void dfs(int i,int j,int k) {
//越界判断
if(i < 0 || i >= arr.length || j < 0 || j >= arr[0].length) {
return;
}
if(arr[i][j] == '.') {
return;
}
//此时情况为找到斑点
if(k == 1) {
map1.add(new int[] {i+1, j+1});
}else {
map2.add(new int[] {i+1, j+1});
}
arr[i][j] = '.';
dfs(i + 1,j,k);dfs(i - 1,j,k);dfs(i,j + 1,k);dfs(i,j - 1,k);
}
}