蓝桥杯每日一题:奶牛选美(DSF)

2024-04-09 21:36
文章标签 每日 蓝桥 奶牛 选美 dsf

本文主要是介绍蓝桥杯每日一题:奶牛选美(DSF),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

听说最近两斑点的奶牛最受欢迎,约翰立即购进了一批两斑点牛。

不幸的是,时尚潮流往往变化很快,当前最受欢迎的牛变成了一斑点牛。

约翰希望通过给每头奶牛涂色,使得它们身上的两个斑点能够合为一个斑点,让它们能够更加时尚。

牛皮可用一个 N×M 的字符矩阵来表示,如下所示:

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

其中,X 表示斑点部分。

如果两个 X 在垂直或水平方向上相邻(对角相邻不算在内),则它们属于同一个斑点,由此看出上图中恰好有两个斑点。

约翰牛群里所有的牛都有两个斑点

约翰希望通过使用油漆给奶牛尽可能少的区域内涂色,将两个斑点合为一个。

在上面的例子中,他只需要给三个 .. 区域内涂色即可(新涂色区域用 ∗∗ 表示):

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....

请帮助约翰确定,为了使两个斑点合为一个,他需要涂色区域的最少数量。

输入格式

第一行包含两个整数 N和 M。

接下来 N 行,每行包含一个长度为 M 的由 X 和 .. 构成的字符串,用来表示描述牛皮图案的字符矩阵。

输出格式

输出需要涂色区域的最少数量。

数据范围

1≤N,M≤50

输入样例:
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....
输出样例:
3

听说最近两斑点的奶牛最受欢迎,约翰立即购进了一批两斑点牛。

不幸的是,时尚潮流往往变化很快,当前最受欢迎的牛变成了一斑点牛。

约翰希望通过给每头奶牛涂色,使得它们身上的两个斑点能够合为一个斑点,让它们能够更加时尚。

牛皮可用一个 N×M�×� 的字符矩阵来表示,如下所示:

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....

其中,X� 表示斑点部分。

如果两个 X� 在垂直或水平方向上相邻(对角相邻不算在内),则它们属于同一个斑点,由此看出上图中恰好有两个斑点。

约翰牛群里所有的牛都有两个斑点

约翰希望通过使用油漆给奶牛尽可能少的区域内涂色,将两个斑点合为一个。

在上面的例子中,他只需要给三个 .. 区域内涂色即可(新涂色区域用 ∗∗ 表示):

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
........XXXXX...
.........XXX....

请帮助约翰确定,为了使两个斑点合为一个,他需要涂色区域的最少数量。

输入格式

第一行包含两个整数 N� 和 M�。

接下来 N� 行,每行包含一个长度为 M� 的由 X� 和 .. 构成的字符串,用来表示描述牛皮图案的字符矩阵。

输出格式

输出需要涂色区域的最少数量。

数据范围

1≤N,M≤501≤�,�≤50

输入样例:
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........XXX....
输出样例:
3

 参考代码:

/*
统计两个团的所有点的坐标,双重遍历一边利用曼哈顿距离找到两图形中最近的两点的距离;
*/
#include<iostream>
#include<algorithm>
#include<vector>#define x first
#define y secondusing namespace std;
typedef pair<int, int> PII;
const int N = 55;
vector<PII> points[2];
int n,m;
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};void dfs(int x,int y,vector<PII> &ps)
{g[x][y] = '.';ps.push_back({x,y});for(int i=0;i<4;i++){int a = x + dx[i] ,b = y + dy[i];if(g[a][b]=='X')dfs(a,b,ps);}
}int main()
{cin>>n>>m;for(int i=0;i<n;i++) cin>>g[i];for(int i=0,k=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='X')dfs(i,j,points[k++]);int res = 1e9;for(auto &a : points[0])for(auto &b :points[1])res = min(res,abs(a.x-b.x)+abs(a.y-b.y)-1);cout<<res;return 0;
}

这篇关于蓝桥杯每日一题:奶牛选美(DSF)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/889276

相关文章

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

每日一题——第八十一题

打印如下图案: #include<stdio.h>int main() {int i, j;char ch = 'A';for (i = 1; i < 5; i++, ch++){for (j = 0; j < 5 - i; j++){printf(" ");//控制空格输出}for (j = 1; j < 2 * i; j++)//条件j < 2 * i{printf("%c", ch

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

英语每日一段 195

Promising economic indicators won’t instantly reverse the lingering impact of hard times for millions of families, workplace culture expert Jessica Kriegel said. “Perception and reality are sometimes

GitHub每日最火火火项目(9.7)

项目名称:polarsource / polar 项目介绍:polar 是一个开源的项目,它是 Lemon Squeezy 的替代方案,具有更优惠的价格。该项目旨在让开发者能够凭借自己的热情进行编码并获得报酬。通过使用 polar,开发者可以更轻松地实现自己的创意和项目,并从中获得收益。 项目地址:https://github.com/polarsource/polar项目名称:psf / bla