《算法竞赛·快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。
文章目录
- 题目描述
- 题解
- 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)