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

Leetcode打卡:棋盘上有效移动组合的数目

执行结果:通过

题目:2056 棋盘上有效移动组合的数目

有一个 8 x 8 的棋盘,它包含 n 个棋子(棋子包括车,后和象三种)。给你一个长度为 n 的字符串数组 pieces ,其中 pieces[i] 表示第 i 个棋子的类型(车,后或象)。除此以外,还给你一个长度为 n 的二维整数数组 positions ,其中 positions[i] = [ri, ci] 表示第 i 个棋子现在在棋盘上的位置为 (ri, ci) ,棋盘下标从 1 开始。

棋盘上每个棋子都可以移动 至多一次 。每个棋子的移动中,首先选择移动的 方向 ,然后选择 移动的步数 ,同时你要确保移动过程中棋子不能移到棋盘以外的地方。棋子需按照以下规则移动:

  • 车可以 水平或者竖直 从 (r, c) 沿着方向 (r+1, c)(r-1, c)(r, c+1) 或者 (r, c-1) 移动。
  • 后可以 水平竖直或者斜对角 从 (r, c) 沿着方向 (r+1, c)(r-1, c)(r, c+1)(r, c-1)(r+1, c+1)(r+1, c-1)(r-1, c+1)(r-1, c-1) 移动。
  • 象可以 斜对角 从 (r, c) 沿着方向 (r+1, c+1)(r+1, c-1)(r-1, c+1)(r-1, c-1) 移动。

移动组合 包含所有棋子的 移动 。每一秒,每个棋子都沿着它们选择的方向往前移动 一步 ,直到它们到达目标位置。所有棋子从时刻 0 开始移动。如果在某个时刻,两个或者更多棋子占据了同一个格子,那么这个移动组合 不有效 。

请你返回 有效 移动组合的数目。

注意:

  • 初始时,不会有两个棋子 在 同一个位置 。
  • 有可能在一个移动组合中,有棋子不移动。
  • 如果两个棋子 直接相邻 且两个棋子下一秒要互相占据对方的位置,可以将它们在同一秒内 交换位置 。

示例 1:

输入:pieces = ["rook"], positions = [[1,1]]
输出:15
解释:上图展示了棋子所有可能的移动。

示例 2:

输入:pieces = ["queen"], positions = [[1,1]]
输出:22
解释:上图展示了棋子所有可能的移动。

示例 3:

输入:pieces = ["bishop"], positions = [[4,3]]
输出:12
解释:上图展示了棋子所有可能的移动。

示例 4:

输入:pieces = ["rook","rook"], positions = [[1,1],[8,8]]
输出:223
解释:每个车有 15 种移动,所以总共有 15 * 15 = 225 种移动组合。
但是,有两个是不有效的移动组合:
- 将两个车都移动到 (8, 1) ,会导致它们在同一个格子相遇。
- 将两个车都移动到 (1, 8) ,会导致它们在同一个格子相遇。
所以,总共有 225 - 2 = 223 种有效移动组合。
注意,有两种有效的移动组合,分别是一个车在 (1, 8) ,另一个车在 (8, 1) 。
即使棋盘状态是相同的,这两个移动组合被视为不同的,因为每个棋子移动操作是不相同的。

示例 5:

输入:pieces = ["queen","bishop"], positions = [[5,7],[3,4]]
输出:281
解释:总共有 12 * 24 = 288 种移动组合。
但是,有一些不有效的移动组合:
- 如果后停在 (6, 7) ,它会阻挡象到达 (6, 7) 或者 (7, 8) 。
- 如果后停在 (5, 6) ,它会阻挡象到达 (5, 6) ,(6, 7) 或者 (7, 8) 。
- 如果象停在 (5, 2) ,它会阻挡后到达 (5, 2) 或者 (5, 1) 。
在 288 个移动组合当中,281 个是有效的。

提示:

  • n == pieces.length
  • n == positions.length
  • 1 <= n <= 4
  • pieces 只包含字符串 "rook" ,"queen" 和 "bishop" 。
  • 棋盘上最多只有一个后。
  • 1 <= ri, ci <= 8
  • 每一个 positions[i] 互不相同。

代码以及解题思路

代码:

int rookDirections[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int bishopDirections[4][2] = {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int queenDirections[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};#define MAX_STACK_SIZE 1024typedef struct {int startX, startY, endX, endY, dx, dy, curX, curY;
} Movement;void initMovement(Movement *obj, int startX, int startY, int endX, int endY, int dx, int dy) {obj->startX = startX;obj->startY = startY;obj->endX = endX;obj->endY = endY;obj->dx = dx;obj->dy = dy;obj->curX = startX;obj->curY = startX;
}// Reset 重置棋子的当前位置
void reset(Movement *obj) {obj->curX = obj->startX;obj->curY = obj->startY;
}// Stopped 判断棋子是否停止
bool stopped(Movement *obj) {return obj->curX == obj->endX && obj->curY == obj->endY;
}// Advance 让棋子按照步长移动
void advance(Movement *obj) {if (!stopped(obj)) {obj->curX += obj->dx;obj->curY += obj->dy;}
}// Cross 判断两个棋子是否相遇
bool cross(Movement *m1, Movement *m2) {// 每次判断是否相遇时需要重置 curreset(m1);reset(m2);while (!stopped(m1) || !stopped(m2)) {advance(m1);advance(m2);if (m1->curX == m2->curX && m1->curY == m2->curY) {return true;}}return false;
}// Check 判断第 u 个棋子是否与之前的棋子发生相交
bool check(int u, Movement *stack) {for (int v = 0; v < u; v++) {Movement *m1 = &stack[u], *m2 = &stack[v];if (cross(m1, m2)) {return false;}}return true;
}void dfs(int u, char** pieces, int piecesSize, int** positions, Movement *stack, int *res) {if (u == piecesSize) {(*res)++;return;}// 处理第 u 个棋子原地不动的情况initMovement(&stack[u], positions[u][0], positions[u][1], positions[u][0], positions[u][1], 0, 0);if (check(u, stack)) {dfs(u + 1, pieces, piecesSize, positions, stack, res);}// 枚举第 u 个棋子在所有方向、所有步数的情况int (*directions)[2];int directionsSize = 0;if (!strcmp(pieces[u], "rook")) {directions = rookDirections;directionsSize = 4;} else if (!strcmp(pieces[u], "queen")) {directions = queenDirections;directionsSize = 8;} else {directions = bishopDirections;directionsSize = 4;}for (int i = 0; i < directionsSize; i++) {for (int j = 1; j < 8; j++) {int x = positions[u][0] + directions[i][0] * j;int y = positions[u][1] + directions[i][1] * j;if (x < 1 || x > 8 || y < 1 || y > 8) {break;}initMovement(&stack[u], positions[u][0], positions[u][1], x, y, directions[i][0], directions[i][1]);if (check(u, stack)) {dfs(u + 1, pieces, piecesSize, positions, stack, res);}}}
}int countCombinations(char** pieces, int piecesSize, int** positions, int positionsSize, int* positionsColSize) {int res = 0;Movement stack[MAX_STACK_SIZE];dfs(0, pieces, piecesSize, positions, stack, &res);return res;}

解题思路:

这个问题是关于在国际象棋棋盘上,给定一些棋子的类型和初始位置,计算它们移动到目标位置(这里假设目标位置是它们能移动到的任意合法位置,不一定是初始位置)的所有可能组合的数量,同时要求任意两个棋子在移动过程中不能相遇。棋子的类型包括车(rook)、象(bishop)和后(queen),每种棋子有不同的移动规则:

  • 车(rook)可以沿直线水平或垂直移动任意步数。
  • 象(bishop)可以沿对角线移动任意步数。
  • 后(queen)可以沿直线或对角线移动任意步数。

解题思路如下:

  1. 定义数据结构
    • 使用 Movement 结构体来表示棋子的移动状态,包括起始位置、结束位置、当前位置、以及移动的方向(dx, dy)。
    • 使用 rookDirectionsbishopDirections 和 queenDirections 数组来定义每种棋子的移动方向。
  2. 初始化
    • initMovement 函数用于初始化棋子的移动状态。
    • reset 函数用于重置棋子的当前位置到起始位置。
    • stopped 函数用于判断棋子是否已到达结束位置。
    • advance 函数用于按步长移动棋子。
  3. 判断相遇
    • cross 函数用于判断两个棋子在移动过程中是否会相遇。它首先重置两个棋子的当前位置,然后按照它们的移动规则逐步移动,如果在任何一步两个棋子的位置相同,则表示它们相遇。
  4. 检查合法性
    • check 函数用于检查在添加一个新的棋子移动方案后,该方案是否与之前的棋子移动方案发生冲突(即是否有棋子相遇)。
  5. 深度优先搜索(DFS)
    • dfs 函数是核心递归函数,用于枚举所有可能的棋子移动组合。
    • 它首先处理每个棋子原地不动的情况。
    • 然后,对于每种棋子和每个方向,它枚举棋子在该方向上移动1到7步(假设棋盘是8x8的)的所有可能情况。
    • 对于每种情况,如果它不与之前的棋子移动方案冲突,则递归地继续处理下一个棋子。
    • 当所有棋子都被处理完毕时,找到一个合法的组合,结果计数加一。
  6. 主函数
    • countCombinations 函数是程序的入口,它初始化结果变量和 Movement 栈,然后调用 dfs 函数开始搜索。
    • 最后,返回计算得到的合法组合数量。

通过这种方式,程序能够枚举所有可能的棋子移动组合,同时确保任意两个棋子在移动过程中不会相遇,从而计算出所有合法的组合数量。

相关文章:

Leetcode打卡:棋盘上有效移动组合的数目

执行结果&#xff1a;通过 题目&#xff1a;2056 棋盘上有效移动组合的数目 有一个 8 x 8 的棋盘&#xff0c;它包含 n 个棋子&#xff08;棋子包括车&#xff0c;后和象三种&#xff09;。给你一个长度为 n 的字符串数组 pieces &#xff0c;其中 pieces[i] 表示第 i 个棋子的…...

生产看板到底在看什么?

说起生产看板&#xff0c;可能很多人脑海里冒出来的画面是&#xff1a;车间里一块挂在墙上的大板子&#xff0c;上面贴满了各式各样的卡片、表格&#xff0c;甚至还有几个闪闪发光的指示灯。但是&#xff0c;无论是精益生产方式代表——丰田&#xff0c;还是当下以“智能制造”…...

12,攻防世界simple_php

simple_php 题目来源:Cyberpeace-n3k0 题目描述: 小宁听说php是最好的语言,于是她简单学习之后写了几行php代码。 进入靶场 这段PHP代码是一个简单的web应用示例&#xff0c;让我们逐步分析这段代码&#xff1a; show_source(__FILE__);&#xff1a;这行代码会显示当前文件的…...

解决Jupyter Notebook无法转化为Pdf的问题(基于Typora非常实用)

笔者在完成各项作业和做笔记时&#xff0c;经常用到jupyter notebook&#xff1b;其因为可以同时运行python并提供格式化的数字公式的输入方式&#xff0c;得到了广大用户的喜爱。 当我们想要将.ipynb文件导出为pdf时&#xff0c;有两种常用方法。 1.Ctrlp 2.通过File ->…...

齐护机器人ModbusRTU RS485转TTL通信模块与ESP32 Arduino通信可Mixly的图形化编程Scratch图形化编程

齐护机器人ModbusRTU RS485-TTL通信模块 一、概念理解 Modbus协议是一种由Modicon公司&#xff08;现为施耐德电气Schneider Electric&#xff09;于1979年发表的网络通信协议&#xff0c;旨在实现可编辑逻辑控制器&#xff08;PLC&#xff09;之间的通信。 1.1 什么是Mod…...

python学习笔记15 python中的类

上一篇我们介绍了python中的库 &#xff0c;学习了一些常见的内置库。详细内容可点击–>python学习笔记14 python中的库&#xff0c;常见的内置库&#xff08;random、hashlib、json、时间、os&#xff09; 这一篇我们来看一下python中的类 创建一个类 class 类的名称():de…...

PMP–一、二、三模、冲刺–分类–10.沟通管理

文章目录 技巧十、沟通管理 一模10.沟通管理--1.规划沟通管理--文化意识--军事背景和非军事背景人员有文化差异5、 [单选] 项目团队由前军事和非军事小组成员组成。没有军事背景的团队成员认为前军事团队成员在他们的项目方法中过于结构化和僵化。前军事成员认为其他团队成员更…...

android-studio开发第一个项目,并在设备上调试

恭喜你成功安装并配置好了 Android Studio&#xff01;下面是开发你的第一个 Android 项目并在设备上调试的详细步骤&#xff1a; 1. 启动 Android Studio 首先&#xff0c;启动 Android Studio。你可以通过以下几种方式启动&#xff1a; 使用桌面快捷方式&#xff08;如果已…...

springboot/ssm线上教育培训办公系统Java代码web项目在线课程作业源码

springboot/ssm线上教育培训办公系统Java代码web项目在线课程作业源码 基于springboot(可改ssm)htmlvue项目 开发语言&#xff1a;Java 框架&#xff1a;springboot/可改ssm vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xff09; 服务器&#xff1a;tomcat 数据库&…...

Spring 依赖 详解

Spring 依赖详解 在 Spring 框架中&#xff0c;依赖 是指一个对象&#xff08;Bean&#xff09;需要另一个对象&#xff08;Bean&#xff09;来完成其功能的情况。Spring 通过 依赖注入&#xff08;Dependency Injection, DI&#xff09; 和 控制反转&#xff08;Inversion of…...

千益畅行,旅游卡有些什么优势?

千益畅行共享旅游卡是一种创新的旅游服务模式&#xff0c;旨在通过整合各类旅游资源&#xff0c;为用户提供一站式的旅游解决方案。这张旅游卡支持2至6人同行&#xff0c;涵盖了接机、酒店、用餐、大巴、导游、景区门票等服务&#xff0c;用户只需自行承担往返交通费用即可享受…...

Ubuntu24 cgroupv2导致rancher(k3s)启动失败的处理

方案一&#xff1a; 修改系统镜像为ubuntu18 方案二&#xff1a; 修改当前系统的cgroup版本&#xff0c;由v2改成v1 修改步骤&#xff1a; 1、查看当前cgroup版本 stat -fc %T /sys/fs/cgroup cgroup v2&#xff0c;输出结果为cgroup2fs cgroup v1&#xff0c;输出为tm…...

学习CSS第二天

学习文章目录 一.内部样式 一.内部样式 写在 html 页面内部&#xff0c;将所有的 CSS 代码提取出来&#xff0c;单独放在 <style> 标签中 语法&#xff1a; <style> h1 { color: red; font-size: 40px; } </style>注意点&#xff1a; <style> 标签理…...

2021数学分析【南昌大学】

2021 数学分析 求极限 lim ⁡ n → ∞ 1 n ( n + 1 ) ( n + 2 ) ⋯ ( n + n ) n \lim_{n \to \infty} \frac{1}{n} \sqrt [n]{(n+1)(n+2) \cdots (n+n)} n→∞lim​n1​n(n+1)(n+2)⋯(n+n) ​ lim ⁡ n → ∞ 1 n ( n + 1 ) ( n + 2 ) ⋯ ( n + n ) n = lim ⁡ n → ∞ ( n + …...

单端和差分信号的接线法

内容来源&#xff1a;【单端信号 差分信号与数据采集卡的【RSE】【 NRES】【 DIFF】 模式的连接】 此篇文章仅作笔记分享。 单端输入 单端信号指的是输入信号由一个参考端和一个信号端构成&#xff0c;参考端一般是地端&#xff0c;信号就是通过计算信号端口和地端的差值所得…...

力扣-图论-2【算法学习day.52】

前言 ###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;&#xff09;我的解析也不会做的非常详细&#xff0c;只会提供思路和一些关键点&#xff0c;力扣上的大佬们的题解质量是非…...

MySQL如何区分幻读和不可重复读

在MySQL中&#xff0c;幻读和不可重复读都是并发事务中可能出现的问题&#xff0c;但它们的表现和原因略有不同。 不可重复读 (Non-Repeatable Read) 不可重复读是指在同一个事务内&#xff0c;多次读取同一行数据时&#xff0c;可能会得到不同的结果。这种情况发生在一个事务…...

界面控件Syncfusion Essential Studio®现在已完全支持 .NET 9

Syncfusion Essential Studio现在完全支持 .NET 9&#xff0c;可最新版本2024 Volume 3 版本中使用&#xff01;通过此更新&#xff0c;Blazor、.NET MAUI、WPF、WinForms、WinUI和ASP.NET Core 平台中的 Syncfusion 组件以及文档处理库已准备好让您利用 .NET 9 中的最新功能。…...

openEuler安装lsb_release

lsb_release是linux下查看发行版信息用的工具 lsb_release只是一个小程序&#xff0c;它的包名并不是lsb_release lsb_release其实是红帽的一个项目&#xff0c;其名为redhat-lsb 我们的lsb_release就是其中的一部分&#xff0c;更准确的说是redhat-lsb-core 从网站&#xff1…...

统计数字字符个数

统计数字字符个数 C语言实现C实现Java实现Python实现 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 输入一行字符&#xff0c;统计出其中数字字符的个数。 输入 一行字符串&#xff0c;总长度不超过255。 输出 出为1行&#xff0c;输出…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中&#xff0c;提供了一系列静态方法用于操作数组&#xff08;如排序、搜索、填充、比较等&#xff09;。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序&#xff08;sort&#xff09; 对数组进行升序…...

八、【ESP32开发全栈指南:UDP客户端】

1. 环境准备 安装ESP-IDF v4.4 (官方指南)确保Python 3.7 和Git已安装 2. 创建项目 idf.py create-project udp_client cd udp_client3. 完整优化代码 (main/main.c) #include <string.h> #include "freertos/FreeRTOS.h" #include "freertos/task.h&…...

nginx部署

配置阿里云yum源 安装如下编译工具 yum install -y gcc gcc-c autoconf automake make #安装使用nginx还得安装nginx所需的一些第三方系统库的支持&#xff0c;比如nginx的静态资源压缩功能所需的gzip lib库&#xff0c;nginx需要支持URL重写&#xff0c;所需的pcre库&…...