当前位置: 首页 > news >正文

【AtCoder】Beginner Contest 377-B.Avoid Rook Attack

Problem Statement

题目链接
There is a grid of 64 64 64 squares with 8 8 8 rows and 8 8 8 columns. Let ( i , j ) (i,j) (i,j) denote the square at the i i i-th row from the top ( 1 ≤ i ≤ 8 ) (1\leq i\leq8) (1i8) and j j j-th column from the left ( 1 ≤ j ≤ 8 ) (1\leq j\leq8) (1j8).

Each square is either empty or has a piece placed on it. The state of the squares is represented by a sequence ( S 1 , S 2 , S 3 , … , S 8 ) (S_1,S_2,S_3,\ldots,S_8) (S1,S2,S3,,S8) of 8 8 8 strings of length 8 8 8. Square ( i , j ) (i,j) (i,j) ( 1 ≤ i ≤ 8 , 1 ≤ j ≤ 8 ) (1\leq i\leq8,1\leq j\leq8) (1i8,1j8) is empty if the j j j-th character of S i S_i Si is ., and has a piece if it is #.

You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.

A piece placed on square ( i , j ) (i,j) (i,j) can capture pieces that satisfy either of the following conditions:

  • Placed on a square in row i i i
  • Placed on a square in column j j j

For example, a piece placed on square ( 4 , 4 ) (4,4) (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?

Constraints

  • Each S i S_i Si is a string of length 8 8 8 consisting of . and # ( 1 ≤ i ≤ 8 ) (1\leq i\leq 8) (1i8).

Input

The input is given from Standard Input in the following format:

S 1 S_1 S1
S 2 S_2 S2
S 3 S_3 S3
S 4 S_4 S4
S 5 S_5 S5
S 6 S_6 S6
S 7 S_7 S7
S 8 S_8 S8

Output

Print the number of empty squares where you can place your piece without it being captured by any existing pieces.

Sample Input 1

...#....
#.......
.......#
....#...
.#......
........
........
..#.....

Sample Output 1

4

The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece without it being captured on 4 4 4 squares: square ( 6 , 6 ) (6,6) (6,6), square ( 6 , 7 ) (6,7) (6,7), square ( 7 , 6 ) (7,6) (7,6), and square ( 7 , 7 ) (7,7) (7,7).

Sample Input 2

........
........
........
........
........
........
........
........

Sample Output 2

64

There may be no pieces on the grid.

Sample Input 3

.#......
..#..#..
....#...
........
..#....#
........
...#....
....#...

Sample Output 3

4

解法

题目中说,假如当前位置有元素,那么当前位置的一行和一列上都不能放其他元素。让我们计算出还有多少个位置可以放元素。

那么,我们使用一个二维 bool 类型的数组存储是否可以放元素。

如果位置 map[i][j] 上有元素,那么就将 st[0][j]st[i][0] 都标记为 true 表示有元素。

统计答案时,只需要有统计没有元素的位置就可以了,即 st[j][0]!st[0][i] 都为 false 即可。

具体代码如下:

在这里插入图片描述

char map[10][10];
bool st[9][9];
void solved() {/* your code */for (int i = 1; i <=8; i ++) {for (int j = 1; j <= 8; j ++) {cin >> map[i][j];if (map[i][j] == '#') {// 在列上标记st[0][j] = 1;// 在行上标记st[i][0] = 1;}}}int sum = 0;for (int i = 1; i <= 8; i ++) {for (int j = 1; j <= 8; j ++) {// 寻找行和列都为 false 的情况if(!st[j][0] && !st[0][i]) sum ++;}}cout << sum << endl;
}

总结

这道题目因为数据规模很小,所以我们可以使用二维数组存标记去题,但是如果数据量规模较大,使用二维数组存起来的方法必然失效。对于数据量规模较大的题目,下次将会分享具体做法。

相关文章:

【AtCoder】Beginner Contest 377-B.Avoid Rook Attack

Problem Statement 题目链接 There is a grid of 64 64 64 squares with 8 8 8 rows and 8 8 8 columns. Let ( i , j ) (i,j) (i,j) denote the square at the i i i-th row from the top ( 1 ≤ i ≤ 8 ) (1\leq i\leq8) (1≤i≤8) and j j j-th column from the lef…...

江协科技STM32学习- P38 软件SPI读写W25Q64

&#x1f680;write in front&#x1f680; &#x1f50e;大家好&#xff0c;我是黄桃罐头&#xff0c;希望你看完之后&#xff0c;能对你有所帮助&#xff0c;不足请指正&#xff01;共同学习交流 &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd;​…...

【Triton 教程】低内存 Dropout

Triton 是一种用于并行编程的语言和编译器。它旨在提供一个基于 Python 的编程环境&#xff0c;以高效编写自定义 DNN 计算内核&#xff0c;并能够在现代 GPU 硬件上以最大吞吐量运行。 更多 Triton 中文文档可访问 →https://triton.hyper.ai/ 在本教程中&#xff0c;您将编…...

npx创建项目时,error fetch failed.TypeError: fetch failed

npx创建项目时&#xff0c;报以下错误&#xff1a; error fetch failed. TypeError: fetch failedat node:internal/deps/undici/undici:12345:11at process.processTicksAndRejections (node:internal/process/task_queues:95:5)at async getTemplateVersion (C:\Users\ymt30…...

《Kotlin实战》-附录

附录 本部分内容只是简单列举下Kotlin应用以便指引进一步深入学习Kotlin。 附录A&#xff1a;构建Kotlin项目 本节只会记录下gradle的应用&#xff0c;其他需要时请自行搜索查看。 A.1 用Gradle构建Kotlin代码的项目 构建Kotlin项目的标准Gradle脚本如下&#xff1a; bui…...

yelp数据集上识别潜在的热门商家

yelp数据集是研究B2C业态的一个很好的数据集&#xff0c;要识别潜在的热门商家是一个多维度的分析过程&#xff0c;涉及用户行为、商家特征和社区结构等多个因素。从yelp数据集里我们可以挖掘到下面信息有助于识别热门商家 用户评分和评论分析 评分均值: 商家的平均评分是反映其…...

【Linux】进程信号全攻略(一)

&#x1f308; 个人主页&#xff1a;Zfox_ &#x1f525; 系列专栏&#xff1a;Linux 目录 一&#xff1a;&#x1f525; 信号的概念 二&#xff1a;&#x1f525; 信号产生的方式 &#x1f98b; 使用键盘&#x1f98b; 系统调用函数&#x1f98b; 软件条件&#x1f98b; 进程异…...

linux文件重命名

Linux文件重命名 文件名显示异常问题出在哪里批量改名扩展 文件名显示异常 跑测CTS&#xff0c;linux环境看跑测结果log file显示没问题&#xff0c;倘若windows下看log file名却显示异常&#xff0c;不太方便操作。 问题出在哪里 linux环境下文件名可以显示正常&#xff0…...

如何选择适合的AWS EC2实例类型

在云计算的世界中&#xff0c;Amazon Web Services&#xff08;AWS&#xff09;提供了丰富的服务&#xff0c;其中Elastic Compute Cloud&#xff08;EC2&#xff09;是最受欢迎的服务之一。选择合适的EC2实例类型对于确保应用程序的性能和成本效益至关重要。我们九河云通过本文…...

【Uniapp】Uniapp Android原生插件开发指北

前言 在uniapp开发中当HBuilderX中提供的能力无法满足App功能需求&#xff0c;需要通过使用Andorid/iOS原生开发实现时&#xff0c;或者是第三方公司提供的是Android的库&#xff0c;这时候可使用App离线SDK开发原生插件来扩展原生能力。 插件类型有两种&#xff0c;Module模…...

【随手笔记】FLASH-W25Q16(三)

#include "bsp_w25q16.h"/*内部函数声明区*/ static HAL_StatusTypeDef bsp_w25q_Transmit(uint8_t * T_pData, uint16_t T_Size); static HAL_StatusTypeDef bsp_w25q_Receive(uint8_t * R_pData, uint16_t R_Size);/*内部函数定义区*//* 函数参数&#xff1a;1、T_…...

2024软件测试面试热点问题

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 大厂面试热点问题 1、测试人员需要何时参加需求分析&#xff1f; 如果条件循序 原则上来说 是越早介入需求分析越好 因为测试人员对需求理解越深刻 对测试工…...

【JAVA】java 企业微信信息推送

前言 JAVA中 将信息 推送到企业微信 // 企微消息推送messageprivate String getMessage(String name, String problemType, String pushResults, Long orderId,java.util.Date submitTime, java.util.Date payTime) {String message "对接方&#xff1a;<font color\…...

介绍一下数组(c基础)(smart 版)

c初期&#xff0c;记住规则&#xff0c;用规则。 我只是介绍规则。&#xff08;有详细版&#xff0c;这适合smart人看&#xff09; 数组&#xff08;同类型&#xff09; int arr[n] {} ; int 是 元素类型。 int arr[n] {} ; arr为标识符。 {} 集合&#xff0c;元素有次…...

Java项目实战II基于Spring Boot的个人云盘管理系统设计与实现(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 一、前言 基于Spring Boot的个人云盘管理系统设计…...

探索数据科学与大数据技术专业本科生的广阔就业前景

随着信息技术的不断发展&#xff0c;数据科学与大数据技术已经成为各大行业的关键推动力。在这样一个数据驱动的时代&#xff0c;越来越多的企业依赖数据来驱动决策、优化运营和创造价值。因此&#xff0c;数据科学与大数据技术专业的本科生在就业市场上具有广阔的前景和多样的…...

微服务架构面试内容整理-Zuul

Zuul 是由 Netflix 开发的一个边缘服务(API 网关),用于动态路由、监控、认证、以及对微服务架构中的请求进行过滤。它在微服务架构中扮演着重要的角色,提供了一种集中管理和控制服务访问的方式。以下是 Zuul 的主要特点、工作原理和使用场景: 主要特点 1. 动态路由: Zuu…...

解决Knife4j 接口界面UI中文乱码问题

1、查看乱码情况 2、修改 编码设置 3、删除 target 文件 项目重新启动 被坑死了...

微服务架构面试内容整理-Sleuth

Spring Cloud Sleuth 是一个分布式追踪工具&#xff0c;用于监控微服务系统中请求的传播情况。它通过在微服务之间传递追踪信息&#xff0c;帮助开发者理解系统的行为&#xff0c;快速定位性能瓶颈和问题。以下是 Sleuth 的主要特点、工作原理和使用场景&#xff1a; 主要特点 …...

Go语言的接口示例

Go语言的接口(interface)是一种轻量级的多态性实现方式,是构建高扩展性、高复用性代码的利器。Go语言的接口非常灵活,不要求显式的实现声明,只要一个类型实现了接口规定的方法,它就可以被视为该接口的实现者。在本篇博客中,我们将通过多个实际示例,探讨Go语言接口的使用…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...