代运营网站,山河集团建设有限公司网站,线下推广方式,开发一个网站的步骤流程《算法竞赛快冲300题》将于2024年出版#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码#xff0c;以中低档题为主#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
连…《算法竞赛·快冲300题》将于2024年出版是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码以中低档题为主适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
连接草坪(II)” 链接
http://oj.ecustacm.cn/problem.php?id1868 题目描述
【题目描述】 在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块草地的总最短路径实际上是344。 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(13, 33, 13)4。但是根据情况1算最短路箭头指向的土地k到3个草地的距离是1、3、1总最短路是131-23这里减2是因为k被算了3次其实只需要算1次。 根据情况1和2算出的结果取它们的最小值就是答案。。 【重点】 DFS的应用 。
C代码 代码分4步 1、标记每个点属于哪个连通块用DFS编码。 2、枚举每块土地计算它到3个草地的最小距离即情况1。 3、计算3个草地之间的最短距离即情况2。 4、在情况1和情况2中找最小值就是答案。 代码的复杂度约为O(NM)。
#includebits/stdc.h
using namespace std;
int n, m;
char Map[55][55]; //存图
int id[55][55],id_cnt0; //id[x][y]id_cnt: 点(x,y)属于第id_cnt个草地,id_cnt1,2,3
vectorpairint,intA[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个草地的最小距离即情况1for(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 i1 3 ? i1 : 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[i1 3 ? i1 : 1] - 2);coutansendl;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 ListListPairInteger, 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 (PairInteger, 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 (PairInteger, 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 PairK, 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_cnt1)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 i1 if i1 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[i1 if i1 3 else 1] - 2)
print(ans)
