《算法竞赛·快冲300题》每日一题：“连接草坪(II)”

《算法竞赛·快冲300题》将于2024年出版，是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码，以中低档题为主，适合入门、进阶。

“ 连接草坪(II)” ，链接： http://oj.ecustacm.cn/problem.php?id=1868

题目描述

【题目描述】 在N×M的地图上，X表示草，.表示土地。
  一个X与上下左右的X相连形成一片草坪。
  现在已知地图上有三片草坪，最少需要将多少个单位上的土地变成草，才能把两块草坪连接成一块草坪。
【输入格式】 输入第一行为正整数N和M，不超过50。
  接下来N行，每行M个字符。
**【输出格式】**输出一个数字表示答案。
【输入样例】

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

【输出样例】

4

---

题解

   题目给出了3块互不连通的草地，问最少把多少块土地变成草，可以把3块草地连成一块草地。考虑两种情况：
  （1）从土地的角度考虑。对任意一块土地坐标(x,y)，分别计算它到3块草地的3个最少土地（最短路径），然后相加，得到土地(x,y)到3块草地的总最短路径count(x,y)。在所有count(x,y)中取最小值，是否就是答案？不一定，因为这些路径可能穿过其它的草地，导致重复计算。例如样例中左上角(0,0)，它到3块草地的最短路径分别是3、11、7，但是它到3块草地的总最短路径实际上是3+4+4。
  （2）从草地的角度考虑。计算任意两块草地之间的最少土地（最短路径），记为Min[]，其中Min[1]是土地（1-2)之间的最短路、Min[2]是土地（2-3)之间的最短路、Min[3]是土地（1-3)之间的最短路。那么是否min(Min[1]+Min[2], Min[2]+Min[3], Min[1]+Min[3]就是答案？不一定，它可能还不如情况（1）算出的最短路。
  例如下图，根据（2）算总最短路，3块草地之间的最短路是1、3、3，总短短路min(1+3, 3+3, 1+3)=4。但是根据情况（1）算最短路，箭头指向的土地k到3个草地的距离是1、3、1，总最短路是1+3+1-2=3，这里减2，是因为k被算了3次，其实只需要算1次。

  根据情况（1）和（2）算出的结果，取它们的最小值，就是答案。。
【重点】 DFS的应用 。

C++代码

   代码分4步：
  1、标记每个点属于哪个连通块，用DFS编码。
  2、枚举每块土地，计算它到3个草地的最小距离，即情况（1）。
  3、计算3个草地之间的最短距离，即情况（2）。
  4、在情况（1）和情况（2）中找最小值，就是答案。
  代码的复杂度约为O(NM)。

#include<bits/stdc++.h>
using namespace std;
int n, m;
char Map[55][55];           //存图
int id[55][55],id_cnt=0;    //id[x][y]=id_cnt: 点(x,y)属于第id_cnt个草地,id_cnt=1,2,3
vector<pair<int,int>>A[4];  //A[i]: 第i个草地中有哪些点
int dir[4][2] = {1,0,0,1,-1,0,0,-1};   //上下左右四个方向
void dfs(int x, int y, int c){  //从(x,y)开始搜它的邻居草地，并标记属于c个草地id[x][y] = c;               //点(x,y)属于第c个草地A[c].push_back(make_pair(x, y));    //这样写更好： A[c].emplace_back(x, y);for(int i = 0; i < 4; i++){         //上下左右4个邻居int nx = x + dir[i][0], ny = y + dir[i][1];   //邻居坐标if(nx < 0 || nx >= n || ny < 0 || ny >= m)  continue;if(Map[nx][ny] == '.')  continue;  //土地不在草地中if(id[nx][ny])          continue;  //这个点已经遍历过dfs(nx, ny, c);                    //继续}
}
int Count(int x, int y, int i){         //计算(x,y)到第i个草地的最短距离int ans = 100;for(auto a : A[i])ans = min(ans, abs(a.first - x) + abs(a.second - y));return ans;
}
int main(){cin >> n >> m;for(int i = 0; i < n; i++)  cin >> Map[i];//1、标记每个点属于哪个连通块for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(Map[i][j] == 'X' && !id[i][j])dfs(i, j, ++id_cnt);int ans = 100;                //答案//2、枚举每块土地，计算它到3个草地的最小距离，即情况（1）for(int i = 0; i < n; i++)     //任意1个土地到其它草地的最小距离for(int j = 0; j < m; j++)if(Map[i][j] == '.')  //如果(i,j)是土地，计算它到3个草地的最小距离ans = min(ans, Count(i,j,1) + Count(i,j,2) + Count(i,j,3) - 2);  
//为什么要 -2 ？因为把自己算了3次，其实只需要算1次//3、计算3个草地之间的最短距离：1-2 2-3 1-3。int Min[4] = {0, 100, 100, 100};  //例如Min[1]是草地1-2的最短距离for(int i = 1; i <= 3; i++){      //第i个草地和第j个草地的最短距离int j = i+1 <= 3 ? i+1 : 1;for(auto &a : A[i])Min[i] = min(Min[i], Count(a.first, a.second, j));}//4、计算连通3个草地的最短距离，找最小值，即情况（2）。并与情况（1）的结果比较。for(int i = 1; i <= 3; i++)ans = min(ans, Min[i] + Min[i+1 <= 3 ? i+1 : 1] - 2);cout<<ans<<endl;return 0;
}

Java代码

import java.util.*;
public class Main {static int n, m, id_cnt = 0;static char[][] Map = new char[55][55];static int[][] id = new int[55][55];static List<List<Pair<Integer, Integer>>> A = new ArrayList<>(4);static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};static void dfs(int x, int y, int c) {id[x][y] = c;A.get(c).add(new Pair<>(x, y));for (int i = 0; i < 4; i++) {int nx = x + dir[i][0], ny = y + dir[i][1];if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;if (Map[nx][ny] == '.') continue;if (id[nx][ny] != 0) continue;dfs(nx, ny, c);}}static int Count(int x, int y, int i) {int ans = 100;for (Pair<Integer, Integer> a : A.get(i)) ans = Math.min(ans, Math.abs(a.getKey() - x) + Math.abs(a.getValue() - y));return ans;}public static void main(String[] args) {Scanner cin = new Scanner(System.in);n = cin.nextInt();m = cin.nextInt();for (int i = 0; i < n; i++) Map[i] = cin.next().toCharArray();for (int i = 0; i < 4; i++) A.add(new ArrayList<>());for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)if (Map[i][j] == 'X' && id[i][j] == 0) dfs(i, j, ++id_cnt);int ans = 100;for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (Map[i][j] == '.') ans = Math.min(ans, Count(i, j, 1) + Count(i, j, 2) + Count(i, j, 3) - 2);int[] Min = {0, 100, 100, 100};for (int i = 1; i <= 3; i++) {int j = i + 1 <= 3 ? i + 1 : 1;for (Pair<Integer, Integer> a : A.get(i)) Min[i] = Math.min(Min[i], Count(a.getKey(), a.getValue(), j));}for (int i = 1; i <= 3; i++) ans = Math.min(ans, Min[i] + Min[i + 1 <= 3 ? i + 1 : 1] - 2);System.out.println(ans);cin.close();}static class Pair<K, V> {public K key;public V value;public Pair(K key, V value) {this.key = key;this.value = value;}public K getKey() {  return key;    }public V getValue() {return value;  }}
}

Python代码

  

n, m = map(int, input().split())
Map = [input() for _ in range(n)]
id, id_cnt = [[0] * m for _ in range(n)], 0
A = [[] for _ in range(4)]
dir = [(1, 0), (0, 1), (-1, 0), (0, -1)]
def dfs(x, y, c):id[x][y] = cA[c].append((x, y))for i in range(4):nx, ny = x + dir[i][0], y + dir[i][1]if nx < 0 or nx >= n or ny < 0 or ny >= m: continueif Map[nx][ny] == '.': continueif id[nx][ny] != 0:    continuedfs(nx, ny, c)
def Count(x, y, i):ans = 100for a in A[i]:ans = min(ans, abs(a[0] - x) + abs(a[1] - y))return ans
for i in range(n):for j in range(m):if Map[i][j] == 'X' and id[i][j] == 0:dfs(i, j, id_cnt+1)id_cnt += 1
ans = 100
for i in range(n):for j in range(m):if Map[i][j] == '.':ans = min(ans, Count(i, j, 1) + Count(i, j, 2) + Count(i, j, 3) - 2)Min = [0, 100, 100, 100]
for i in range(1, 4):j = i+1 if i+1 <= 3 else 1for a in A[i]:Min[i] = min(Min[i], Count(a[0], a[1], j))
for i in range(1, 4):ans = min(ans, Min[i] + Min[i+1 if i+1 <= 3 else 1] - 2)
print(ans)