马能否走遍棋盘的可达性证明
而题目本身要求输出 个答案仅输出就至少需要所以对于原题BFS 已经达到最优复杂度量级。不过继续考虑两个问题如果只询问到某一个点的距离是否存在直接公式是否存在马永远到不了的点显然这两个问题必须区分有限棋盘与无限棋盘。一、无限棋盘上的单点最短距离公式将起点平移到原点 目标点记为 。由于马步关于坐标轴和直线 对称只需令于是总有在无限棋盘上最短步数为其他情况其中先计算再按照奇偶性修正例如目标位移最少步数这个公式中的三个限制马的一步位移为首先较大的坐标差每一步最多减少 因此其次坐标绝对值之和每一步最多减少 因此所以最后马每走一步坐标和的奇偶性都会翻转。因为一步中坐标和的变化量一定是奇数因此若走 步到达 必须满足所以当 与 奇偶性不同时还需要再加一步。两个特殊点 与 属于距离过小造成的局部例外需要单独处理。例如因此从原点到 可以三步到达但不可能更少。二、为什么这个公式不能解决原题上面的公式针对的是无限棋盘。原题中的棋盘存在边界而无限棋盘上的最短路径可能会暂时跳出矩形区域。例如在无限棋盘上所以从 到 可以两步到达。但在 棋盘中 已经越界这条路径不合法。事实上中心点 没有任何合法马步与其他位置连接。从左上角出发时距离表为因此无限棋盘上的最短距离有限棋盘上的最短距离有限棋盘中边界会改变整张马步图的结构所以原题仍应使用 BFS。三、无限棋盘上有没有永远到不了的点没有。这个结论可以直接通过生成元证明。把所有整数格点组成的集合视为加法群马的一步能够产生的位移向量为记这些向量生成的子群为只需证明因为 与 生成整个 。首先所以对应路径为其次所以对应路径为于是对任意整数点 都有因此即无限棋盘上马可以到达任意整数格点。四、尝试黑白染色将棋盘按照 的奇偶性染成黑白两色。马每走一步 的奇偶性都会翻转因此格子颜色也会翻转。所以如果目标点与起点同色则所需步数一定为偶数如果目标点与起点异色则所需步数一定为奇数。即但是这只能限制步数的奇偶性不能证明某个点不可达。例如 与原点异色所以它必须经过奇数步到达而它确实可以在三步后到达因此在无限棋盘上染色法约束步数奇偶但不产生不可达点。五、有限矩形棋盘什么时候连通考虑一个没有障碍物的 矩形棋盘不妨设结论为的马步图连通或且换言之除单格棋盘外不连通的矩形棋盘只有下面分别证明。六、 棋盘不连通如果棋盘只有一行马不存在任何合法移动。因为马的一步至少需要跨越两行或三行而棋盘中只有一行。因此当 时每个格子都是孤立点不连通七、 棋盘不连通如果棋盘只有两行马的一步不可能让行号变化 否则会越界。因此合法移动只能满足行列也就是说列编号每次只能变化 于是列编号的奇偶性保持不变。第 列第 列第 列第 列第 列第 列奇偶奇偶奇偶奇偶奇偶奇偶从奇数列出发永远到不了偶数列从偶数列出发永远到不了奇数列。因此不连通这里的不变量是列编号模的余数八、 棋盘不连通考虑中心点 。从中心点出发马无论走还是都会越界。所以中心点没有任何邻点。由于马步可逆也没有任何其他点能够到达中心点。孤立点因此不连通九、 棋盘连通下面给出一条经过全部十二个格子的合法路径。表格中的数字表示访问顺序
相关新闻
2026/6/28 3:15:18
毕业论文AI工具避坑大全：乱编文献、机翻生硬问题怎么规避？
毕业季论文审核正式进入了“双重红线时代”——查重率要达标，AIGC疑似率更要达标。知网、维普等主流检测系统全面升级AIGC检测算法，不仅查文字相似度，更查句式逻辑、写作指纹和人机混合痕迹。与此同时，通用AI工具生成论文时暴露出…
阅读更多
2026/6/28 3:15:18
红外与可见光图像融合方向科研方法2
本文档整理了红外与可见光图像融合方向的期刊会议推荐、投稿准备路线、数据集选择、基线模型选择等全套内容，适合想发A类会议或一区期刊的同学参考。 📚 一、一区期刊完整汇总 1.1 主流可投一区期刊（16本，按难度排序） 序号 期刊名称 影响因子 等级/分区 难度 特点说明 1…
阅读更多
2026/6/28 3:15:18
第10课：自定义 GDB 调试命令
在某些场景下，我们需要根据自己的程序情况，制定一些可以在调试时输出程序特定信息的命令，这在 GDB 中很容易做到，只要在 Linux 当前用户家（home）目录下，如 root 用户是 “/root” 目录ÿ…
阅读更多
2026/6/28 5:05:23
《龙虾软件云部署的优化指南》
工业云平台的分布式架构与多租户特性，在带来弹性算力、灵活部署优势的同时，也天然带来了网络时延波动、资源争抢、数据边界模糊等新的挑战。想要让龙虾软件在云平台上既跑得稳又跑得安全，不能靠通用的云优化方案生搬硬套，必须贴合…
阅读更多
2026/6/28 5:05:23
关于如何使用 *Bash* *别名* 的快速 *指南*
Bash 别名 充当命令行的快捷方式。这是一种方便的方式，可以简化你经常使用的非常长且重复的命令。 Bash alias 命令允许在字符串用作命令行的第一个单词时进行替换。shell 维护一个别名列表，可以使用 Bash alias 和 unalias 内置命令进行设置和取消设置。 如何设置 Bash 别…
阅读更多
2026/6/28 5:05:23
基于ONNXRuntime C#实现的高性能YOLO推理框架
功能特色 支持所有YOLO任务：目标检测、图片分类、实例分割、姿势估计、OBB支持多种部署方案：CPU, CUDA / TensorRT, OpenVINO, CoreML, DirectML可以批量检测图片，性能大幅优于单线程串行执行图像处理使用OpenCVSharp推理引擎：ON…
阅读更多
2026/6/28 5:05:23
《龙虾软件与LIMS对接的落地经验分享》
制造体系里，质检环节始终是生产数据流中最顽固的孤岛节点。上游生产端的工艺参数、批次溯源信息无法自然流入实验室体系，实验室输出的检测结果与质量报告，又始终滞后于生产节拍，难以实时反哺现场调度与工艺调整。这些链路断点带来…
阅读更多)
2026/6/28 5:05:23
【Springboot毕设全套源码+文档】基于SpringBoot的职工健康监护管理系统的设计与实现(丰富项目+远程调试+讲解+定制)
博主介绍：✌️码农一枚 ，专注于大学生项目实战开发、讲解和毕业🚢文撰写修改等。全栈领域优质创作者，博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战 ✌️技术范围：&am…
阅读更多
2026/6/28 5:00:23
2026上海小程序开发公司排行：哪家好？商城、会员与预约项目怎么选
2026上海小程序开发公司排行：哪家好？商城、会员与预约项目怎么选 上海企业做小程序，已经不只是为了展示品牌和联系方式。对于连锁门店、品牌零售、教育培训、企业服务、美业、医疗咨询、招商加盟和本地生活类项目来说，小程序往往承…
阅读更多
2026/6/28 0:00:06
AI Coding 六个月真实ROI账本：产品经理的血泪教训，研发的冷静忠告
6个月前的2025年12月，Boris Cherny 公开宣布自己卸载了 IDE。一时间，Vibe Coding 成了全行业最热的话题。6个月后，当我们回过头来拉一份真实账本，发现事情远没有"一句话生成一个App"那么浪漫。本文从产品经理和研发两个…
阅读更多
2026/6/28 0:00:06
审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？
引言：审计结束三个月了，审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间，内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中，审计…
阅读更多
2026/6/28 0:00:06
AI Coding 六个月真实ROI账本：产品经理的血泪教训，研发的冷静忠告
6个月前的2025年12月，Boris Cherny 公开宣布自己卸载了 IDE。一时间，Vibe Coding 成了全行业最热的话题。6个月后，当我们回过头来拉一份真实账本，发现事情远没有"一句话生成一个App"那么浪漫。本文从产品经理和研发两个…
阅读更多
2026/6/28 0:00:06
审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？
引言：审计结束三个月了，审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间，内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中，审计…
阅读更多