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

算法竞赛·快冲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)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/79623.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[Docker实现测试部署CI/CD----自由风格的CI操作[中间架构](4)]

目录 10、自由风格的CI操作&#xff08;中间架构&#xff09;中间架构图创建web项目Idea提交项目到远程仓库提交代码到本地库提交代码到远程库从jenkins拉取代码新建任务jenkins集成gitlab立即构建 将项目打为jar包Jenkins 配置 mvn 命令重新构建 代码质量检测jenkins将代码推送…

HTTP(超文本传输协议)学习

关于HTTP补学 一、HTTP能干什么 通过下图能够直观的看出&#xff1a;“交换数据 ” 二、HTTP请求例子 一个 HTTP 方法&#xff0c;通常是由一个动词&#xff0c;像 GET、POST 等&#xff0c;或者一个名词&#xff0c;像 OPTIONS、HEAD 等&#xff0c;来定义客户端执行的动作。…

小学语文思维导图:如何写一篇好的作文

大家都知道&#xff0c;思维导图是一款非常高效的工具。我们利用思维导图不仅可以做读书笔记、还可以运用到很多具体细分的场景。今天我们就“如何利用思维导图写好一篇作文”和大家进行分享。 思维导图在写作文的过程中&#xff0c;可以帮助我们整理思路。提高效率。将混乱的内…

【iOS安全】OpenSSH使用

安装OpenSSH 在 Cydia 中直接查找和安装 OpenSSH 使用OpenSSH http://orinchen.github.io/blog/2014/01/15/install-and-use-openssh-on-ios/ 保证PC和iPhone在同一网段下 查看iPhone的IP地址 ssh root10.168.xx.xx 口令默认是alpine 或者也可以使用XShell等集成终端

再次斩获第一,文心3.5霸榜国内大模型

目录 1 什么是文心一言&#xff1f;2 体验与文心一言对话3 文心3.5霸榜国内大模型 1 什么是文心一言&#xff1f; 文心一言是百度全新一代知识增强大语言模型&#xff0c;文心大模型家族的新成员&#xff0c;能够与人对话互动&#xff0c;回答问题&#xff0c;协助创作&#xf…

数据结构--单链表OJ题

上文回顾---单链表 这章将来做一些链表的相关题目。 目录 1.移除链表元素 2.反转链表 3.链表的中间结点 4.链表中的倒数第k个结点 5.合并两个有序链表 6.链表分割 7.链表的回文结构 8.相交链表 9.环形链表 ​编辑 10.环形链表II ​编辑 ​编辑 1.移除链表元素 思…

2023暑假牛客多校6- E.Sequence

题目描述 You have an array of elements . For each task, you have three integers . Ask whether you can find an array of integers satisfy: are the multiplies of 2 Specially, if , it should satisfy is the multiply of 2 We define . If possible, print…

Java课题笔记~ 动态SQL详解

一、动态 sql 是什么&#xff1f; 1、动态 SQL 是 MyBatis 的强大特性之一。在 JDBC 或其它类似的框架中&#xff0c;开发人员通常需要手动拼接 SQL 语句。根据不同的条件拼接 SQL 语句是一件极其痛苦的工作。 例如&#xff0c;拼接时要确保添加了必要的空格&#xff0c;还要…

cnvd通用型证书获取姿势

因为技术有限&#xff0c;只能挖挖不用脑子的漏洞&#xff0c;平时工作摸鱼的时候通过谷歌引擎引擎搜索找找有没有大点的公司有sql注入漏洞&#xff0c;找的方法就很简单&#xff0c;网站结尾加上’&#xff0c;有异常就测试看看&#xff0c;没有马上下一家&#xff0c;效率至上…

Day12-1-Webpack前端工程化开发

Webpack前端工程化 1 案例-webpack打包js文件 1 在index.html中编写代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><me…

20天学会rust(二)rust的基础语法篇

在第一节&#xff08;20天学rust&#xff08;一&#xff09;和rust say hi&#xff09;我们配置好了rust的环境&#xff0c;并且运行了一个简单的demo——practice-01&#xff0c;接下来我们将从示例入手&#xff0c;学习rust的基础语法。 首先来看下项目结构&#xff1a; 项目…

QtWebApp开发https服务器,完成客户端与服务器基于ssl的双向认证,纯代码操作

引言&#xff1a;所谓http协议&#xff0c;本质上也是基于TCP/IP上服务器与客户端请求和应答的标准&#xff0c;web开发中常用的http server有apache和nginx。Qt程序作为http client可以使用QNetworkAccessManager很方便的进行http相关的操作。Qt本身并没有http server相关的库…

zabbix监控mysql容器主从同步状态并告警钉钉/企业微信

前言&#xff1a;被监控的主机已经安装和配置mysql主从同步&#xff0c;和zabbix-agent插件。 mysql创建主从同步&#xff1a;http://t.csdn.cn/P4MYq centos安装zabbix-agent2&#xff1a;http://t.csdn.cn/fx74i mysql主从同步&#xff0c;主要监控这2个参数指标&#xf…

Maven-学习笔记

文章目录 1. Maven简介2.Maven安装和基础配置3.Maven基本使用4.Maven坐标介绍 1. Maven简介 概念 Maven是专门用于管理和构建Java项目的工具 主要功能有: 提供了一套标准化的项目结构提供了一套标准化的构建流程&#xff08;编译&#xff0c;测试&#xff0c;打包&#xff0c;…

微信小程序中的全局数据共享(状态管理)使用介绍

开发工具&#xff1a;微信开发者工具Stable 1.06 一、状态管理简介 微信小程序全局状态是指可以在不同页面之间共享的数据或状态。 它可以存储用户的登录状态、个人信息、全局配置信息等。 二、安装MobX 1、安装NPM 在资源管理器的空白地方点右键&#xff0c;选择“在外部…

无涯教程-Perl - endhostent函数

描述 此函数告诉系统您不再希望使用gethostent从hosts文件读取条目。 语法 以下是此函数的简单语法- endhostent返回值 此函数不返回任何值。 例 以下是显示其基本用法的示例代码- #!/usr/bin/perlwhile( ($name, $aliases, $addrtype, $length, addrs)gethostent() ) …

5个可以创意灵感的AI绘画工具

当设计灵感耗尽&#xff0c;陷入创作瓶颈时&#xff0c;人工智能艺术生成器可能会为您提供新的启示。这些基于深度学习和发展“神经网络”的工具可以将输入的文本描述或图像转换成各种风格的艺术作品&#xff0c;并提供丰富的风格参数和材料库&#xff0c;让您可以自由调整和创…

【Linux】网络套接字知识点补足

目录 1 地址转换函数 1.1 字符串转in_addr的函数: 1.2 in_addr转字符串的函数: 1.3 关于inet_ntoa 2 TCP协议通讯流程 1 地址转换函数 本节只介绍基于IPv4的socket网络编程,sockaddr_in中的成员struct in_addr sin_addr表示32位 的IP 地址但是我们通常用点分十进制的字符串…

【Java split】split() 函数分割空字符串后数组长度为1的原因以及规避措施(105)

问题现象: import java.util.ArrayList; import java.util.Arrays; import java.util.List;public class test06 {public static void main(String[] args) {// Java split()函数 分割空字符串长度为1的解释&#xff1b;String s2 "";String[] arr2 s2.split(&quo…

Spring 容器原始 Bean 是如何创建的?

以下内容基于 Spring6.0.4。 这个话题其实非常庞大&#xff0c;我本来想从 getBean 方法讲起&#xff0c;但一想这样讲完估计很多小伙伴就懵了&#xff0c;所以我们还是一步一步来&#xff0c;今天我主要是想和小伙伴们讲讲 Spring 容器创建 Bean 最最核心的 createBeanInstan…