P3654 First Step (ファーストステップ)(贪心算法)

embedded/2025/2/11 19:51:59/

 

#include<bits/stdc++.h> 
using namespace std;int main() {int r,c,k;cin>>r>>c>>k;char a[105][105];int ans=0;for(int i=0;i<r;i++){for(int j=0;j<c;j++){cin>>a[i][j];}}for(int i=0;i<r;i++){int cnt=0; // 用来记录连续空地的数量for(int j=0;j<c;j++){if(a[i][j]=='.'){cnt++; // 如果是空地,连续空地计数增加} else{if(cnt>=k) ans+=cnt-k+1;// 连续空地数大于等于 K 时,可以放置队员cnt=0; // 重置连续空地计数}}if(cnt>=k){ // 行末还有连续空地的情况,需要处理ans+=cnt-k+1;}}for(int j=0;j<c;j++){int cnt=0;for(int i=0;i<r;i++){if(a[i][j]=='.'){cnt++;} else{if(cnt>=k) ans+=cnt-k+1;cnt=0;}}if(cnt>=k) ans+=cnt-k+1;}if(k==1) ans/=2;// 如果 K == 1,则需要除以 2,因为每个空地计算了两次cout<<ans;}

 水平扫描(按行)

  • 对每一行进行扫描,累积每段连续的空地数量。
  • 当遇到杂物(#)时,检查当前空地段的长度 cnt 是否大于等于 k,如果满足条件,则可以放置队员,且可以从中选 cnt - k + 1 个位置。
  • 对每行扫描完后,检查该行末尾是否存在连续的空地段(例如 ...),并更新答案。

垂直扫描(按列):

  • 对每一列进行类似的操作,累积连续空地并检查可行的站位方式。

注意:如果 k == 1,则每个空地点都会被统计两次。因此,最终答案需要除以 2。


http://www.ppmy.cn/embedded/161405.html

相关文章

5分钟搭建企业级AI问答知识库

5分钟搭建企业级AI问答知识库 基础概念部署过程使用体验 基础概念 在开始搭建企业级AI问答知识库之前&#xff0c;先来了解一下今天操作过程中用到的三个概念&#xff1a; 概念一&#xff1a;模型在线服务PAI-EAS&#xff08;Elastic Algorithm Service&#xff09;是模型在线…

计算机毕业设计hadoop++hive微博舆情预测 微博舆情分析 微博推荐系统 微博预警系统 微博数据分析可视化大屏 微博情感分析 微博爬虫 知识图谱

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…

STM32启动过程概述

1. STM32启动过程概述 STM32 微控制器的启动过程是指从上电或复位开始&#xff0c;到系统开始执行用户程序的整个过程。这个过程包括了硬件初始化、引导加载程序 (Bootloader) 执行、系统时钟配置、外设初始化等步骤。 2. STM32 启动的基本流程 上电或复位 STM32 芯片的启动过…

教育机器人的智能驱动:揭秘舵机技术的无限可能

在这个科技日新月异的时代&#xff0c;教育机器人正逐渐成为学生们探索科技世界的新窗口。它们不仅承载着编程与机械知识的融合&#xff0c;更以其独特的智能驱动方式&#xff0c;引领着下一代对科技的兴趣与探索。而在这场科技教育的盛宴中&#xff0c;舵机以其高精度和可靠性…

CRM系统中的数据分析和报表功能如何帮助企业?

CRM系统中的数据分析和报表功能&#xff1a;企业战略决策的得力助手 在当今竞争激烈的商业环境中&#xff0c;企业要想保持竞争力并实现持续增长&#xff0c;必须依靠精准的数据分析来制定有效的战略决策。而客户关系管理&#xff08;CRM&#xff09;系统的数据分析与报表生成…

openCV函数使用(一)

读取图像&#xff1a; 中文路径乱码问题&#xff1a; QString filepath QFileDialog::getOpenFileName(this, str); QByteArray cdata filepath.toLocal8Bit();读取灰度图像&#xff1a; imread(std::string(cdata), cv::IMREAD_GRAYSCALE);读取彩色图像&#xff1a; imre…

探索 Amazon Aurora DSQL:基本操作全解析(系列①)

1. 引言 在业务中&#xff0c;我使用 Aurora Global Database (PostgreSQL)&#xff0c;通常配置为 东京&#xff08;Act&#xff09; 和 大阪&#xff08;Sby&#xff09;&#xff0c;以便在灾害或大规模故障发生时能够进行系统切换。 在 Aurora DSQL 中&#xff0c;两个区域…

在OAS中设计简单抬头显示器

在OAS中设计简单抬头显示器 本文演示了如何使用OAS工具设计抬头显示器。 简介 车载HUD是一种将关键信息投射到驾驶员前方视野中的设备&#xff0c;使驾驶员无需低头即可获取车辆状态和导航等数据。构建车载HUD的理论模型时&#xff0c;需综合考虑光学系统、投影技术、人机交…