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

Leetcode 3283. Maximum Number of Moves to Kill All Pawns

  • Leetcode 3283. Maximum Number of Moves to Kill All Pawns
    • 1. 解题思路
    • 2. 代码实现
  • 题目链接:3283. Maximum Number of Moves to Kill All Pawns

1. 解题思路

这一题坦率地说没有想到什么好的思路,因此只能非常暴力地按照题意进行了一下构造。

显然,这个题目可以拆分为两个小题目:

  1. 给出任意 50 × 50 50\times50 50×50的棋盘上的两个点A和B,求令马从点A跳到点B所需的最小步数。
  2. Alice和Bob的吃兵游戏。

其中,前者本应有一些比较漂亮的解答的,这里我倒是没有想到啥好的,最后就是暴力的走了一个宽度优先的遍历。

而关于第二小题,我们的解法则更加暴力,就是分别构造了两个耦合的动态规划算法来翻译了一下题目的过程,其伪代码如下:

def dp_alice(position, status):if status == 2**n-1:return 0return max(step(position, points[i]) + dp_bob(points[i], status | (1 << i)) for i in range(n) if status & (1 << i) == 0)def dp_bob(position, status):if status == 2**n-1:return 0return min(step(position, points[i]) + dp_alice(points[i], status | (1 << i)) for i in range(n) if status & (1 << i) == 0)

这里,我们用一个整数的二进制上的位来记录每一个坐标位置 i i i上的兵是否已经被吃掉了。

2. 代码实现

给出最终的python代码实现如下:

@lru_cache(None)
def move(x0, y0, x1, y1):dirs = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]if abs(x0-x1) == 2 * abs(y0-y1):return abs(y0-y1)if abs(y0-y1) == 2 * abs(x0-x1):return abs(x0-x1)q = [(0, abs(x0-x1) + abs(y0-y1), x0, y0)]seen = {(x0, y0)}while q:step, _, x, y = heapq.heappop(q)for dx, dy in dirs:if x + dx == x1 and y+dy == y1:return step+1if 0 <= x+dx < 50 and 0 <= y+dy < 50 and (x+dx, y+dy) not in seen:seen.add((x+dx, y+dy))heapq.heappush(q, (step+1, abs(x+dx-x1) + abs(y+dy-y1), x+dx, y+dy))return math.infclass Solution:def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:n = len(positions)END = 2**n-1@lru_cache(None)def dp_alice(x, y, status):if status == END:return 0ans = 0for i in range(n):if status & (1 << i) != 0:continuex1, y1 = positions[i][0], positions[i][1]ans = max(ans, move(x, y, x1, y1) + dp_bob(x1, y1, status | (1 << i)))return ans@lru_cache(None)def dp_bob(x, y, status):if status == END:return 0ans = math.inffor i in range(n):if status & (1 << i) != 0:continuex1, y1 = positions[i][0], positions[i][1]ans = min(ans, move(x, y, x1, y1) + dp_alice(x1, y1, status | (1 << i)))return ansreturn dp_alice(kx, ky, 0)

提交代码评测得到:耗时11035ms,占用内存119MB。

相关文章:

Leetcode 3283. Maximum Number of Moves to Kill All Pawns

Leetcode 3283. Maximum Number of Moves to Kill All Pawns 1. 解题思路2. 代码实现 题目链接&#xff1a;3283. Maximum Number of Moves to Kill All Pawns 1. 解题思路 这一题坦率地说没有想到什么好的思路&#xff0c;因此只能非常暴力地按照题意进行了一下构造。 显然…...

智能物流新“黑神话”:各位“天命人”,这份行业应用锦集请收下!

全球工业革新浪潮中&#xff0c;智能物流正成为制造业转型升级的核心驱动力之一。高柔性的智能物流解决方案可以帮助企业应对复杂的物流挑战&#xff0c;实现生产到仓储全过程的智能化、柔性化和高度集成&#xff0c;带来显著的经济效益。 作为行业领先的全场景柔性物流综合解…...

SpringSecurity原理解析(五):HttpSecurity 类处理流程

1、SpringSecurity 在spring boot中与SSM项目中基于配置文件的区别 通过前边的笔记我们可以知道&#xff0c;在传统的SSM项目中 SpringSecurity的使用是基于配置文件 的&#xff0c;然后spring 容器初始化的时候将 SpringSecurity 中的各种标签解析成对应的Bean对象&#xff0c…...

C++系列-匿名对象

匿名对象 &#x1f4a2;什么是匿名对象&#x1f4a2;匿名对象的创建方式及作用域&#x1f4a2;匿名对象的对象类型&#x1f4a2;&#x1f4a2;匿名的基本数据类型对象&#x1f4a2;&#x1f4a2;匿名的自定义的类类型对象&#x1f4a2;&#x1f4a2;匿名的标准库的类对象 &…...

tofixed和math.round什么区别

1、floor 返回不大于的最大整数&#xff08;向下取整&#xff09; 2、round 则是4舍5入的计算&#xff0c;入的时候是到大于它的整数&#xff08;当-1.5时可见&#xff0c;四舍五入后得到的结果不是我们期待的&#xff0c;解决办法是先对他取绝对值&#xff0c;然后在用round方…...

OPENAIGC开发者大赛高校组金奖 | 基于混合大语言模型与多模态的全过程通用AI Agent

在第二届拯救者杯OPENAIGC开发者大赛中&#xff0c;涌现出一批技术突出、创意卓越的作品。为了让这些优秀项目被更多人看到&#xff0c;我们特意开设了优秀作品报道专栏&#xff0c;旨在展示其独特之处和开发者的精彩故事。 无论您是技术专家还是爱好者&#xff0c;希望能带给您…...

MySql批量迁移数据库

导出数据库 将指定数据库实例&#xff08;MYSQL_HOST、MYSQL_PORT、MYSQL_USER、MYSQL_PASSWORD&#xff09;中的所有数据库&#xff08;表结构、数据&#xff09;导出到指定目录&#xff08;BACKUP_DIR&#xff09;下的多个单独的SQL脚本&#xff0c;每个SQL脚本名称即为数据…...

一、selenium自动化简介selenium工具集

文章目录 一、简介二、组成部分三、selenium工具集3.1 Selenium IDE3.2 Selenium WebDriver3.3 Selenium Grid3.4 Appium 一、简介 官方网站 Selenium 是支持 web 浏览器自动化的一系列工具和库的综合项目。 它提供了扩展来模拟用户与浏览器的交互&#xff0c;用于扩展浏览器分…...

CCF推荐B类会议和期刊总结:(计算机网络领域)

CCF推荐B类会议和期刊总结&#xff08;计算机网络领域&#xff09; 在计算机网络领域&#xff0c;中国计算机学会&#xff08;CCF&#xff09;推荐的B类会议和期刊代表了该领域的较高水平。以下是对所有B类会议和期刊的总结&#xff0c;包括全称、出版社、dblp文献网址以及所属…...

[Web安全 网络安全]-文件包含漏洞

文章目录&#xff1a; 一&#xff1a;前言 1.什么是文件包含漏洞 2.文件包含漏洞的成因 3.文件包含漏洞的分类 4.文件包含漏洞的防御策略 5.文件包含函数&#xff08;触发点Sink&#xff09; 6.环境 6.1 靶场 6.2 其他工具 二&#xff1a;文件包含LFI labs靶场实验…...

使用soui4实现一个拾色器

拾色器类 #pragma once class CClrPickerCtrl : public SWindow {DEF_SOBJECT(SWindow, L"clrpicker") public:CClrPickerCtrl(void);~CClrPickerCtrl(void);//跟solider控件设置色调void SetSliderPos(int nPos);//获取选取位置的颜色COLORREF GetColor(); protect…...

Thinkphp5 + Swoole实现邮箱异步通知

在 ThinkPHP 中实现邮箱异步通知的常见做法是通过队列系统来处理异步任务&#xff0c;结合 Swoole 来处理异步发送邮件的请求。这样可以避免同步处理邮件发送导致的阻塞&#xff0c;提高响应速度。 以下是基于 ThinkPHP5 框架和 Swoole 的异步邮件通知实现步骤&#xff1a; 一…...

LLM - 理解 多模态大语言模型 (MLLM) 的预训练与相关技术 (三)

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/142063880 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 完备(F…...

工具篇之Joda-Time

在Java应用程序开发中&#xff0c;处理日期和时间是一项常见且复杂的任务。尽管Java标准库提供了基本的日期和时间操作类&#xff0c;但它们的使用常常不够直观和灵活。Joda-Time 是一个强大的日期和时间库&#xff0c;提供了丰富的API&#xff0c;用于简化日期和时间的操作。本…...

架构师应该懂得东西,软考应该具备的

架构师应该懂得知识 架构师作为软件系统设计和开发的关键角色&#xff0c;需要掌握广泛的知识和技能。具体来说&#xff0c;他们应该懂得以下几方面的知识&#xff1a; 编程语言&#xff1a;掌握至少一种编程语言&#xff0c;如Java、C、Python等&#xff0c;以便于进行系统设…...

图论篇--代码随想录算法训练营第五十一天打卡| 99. 岛屿数量(深搜版),99. 岛屿数量(广搜版),100. 岛屿的最大面积

99. 岛屿数量&#xff08;深搜版&#xff09; 题目链接&#xff1a;99. 岛屿数量 题目描述&#xff1a; 给定一个由 1&#xff08;陆地&#xff09;和 0&#xff08;水&#xff09;组成的矩阵&#xff0c;你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而…...

什么是API网关(API Gateway)?

1. 什么是API网关&#xff08;API Gateway&#xff09;&#xff1f; 在微服务体系结构中&#xff0c;客户端可能与多个前端服务进行交互。 API 网关位于客户端与服务之间。 它充当反向代理&#xff0c;将来自客户端的请求路由到服务。 它还可以执行各种横切任务&#xff0c;例…...

对话:LLC磁集成能否成为充电桩模块电源常态产品?

编者按&#xff1a;在终端需求疲软的影响下&#xff0c;前两年火热的新能源汽车、光伏、储能等新能源领域也掀起了价格战&#xff0c;储能已正式进入0.5元时代&#xff0c;新能源汽车领域价格战更是一轮接一轮&#xff0c;成本管控成为2024年企业绕不开的话题。 接下来我们将围…...

基于SSM的二手物品交易管理系统的设计与实现 (含源码+sql+视频导入教程+文档+PPT)

&#x1f449;文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1 、功能描述 基于SSM的二手物品交易管理系统7拥有两种角色 管理员&#xff1a;用户管理、分类管理、商品管理、订单管理、系统管理等 用户&#xff1a;登录注册、充值、收货、评价、收藏、购物车、订…...

视觉语言模型中的人脸社会感知

本文研究了视觉语言模型CLIP在处理人脸图像时的社会感知能力及其潜在偏见。研究者们构建了一个名为CausalFace的合成人脸数据集&#xff0c;通过系统地独立变化年龄、性别、人种、面部表情、照明和姿势等六个维度来评估模型的社会感知。他们发现&#xff0c;尽管CLIP是在多样化…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...