首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

java 实现棋盘覆盖问题

问题描述:在一个2k*2k的棋盘中,有一个特殊方格,要求用L型骨牌覆盖满除特殊方格外的所有其他方格,且骨牌不得重叠....所以将2k*2k的棋盘,先分成相等的四块子棋盘,其中特殊方格位于四个中的一个,构造剩下没特殊方格三个子棋盘:将一块骨牌放在这三个小棋盘的交界处,使骨牌的每一个方格都作为三个小棋盘的特殊方格,骨牌具体放法如下...: 左上的子棋盘若不存在特殊方格,将该子棋盘右下角的那个方格覆盖为特殊方格 右上的子棋盘若不存在特殊方格,将该子棋盘左下角的那个方格覆盖为特殊方格 左下的子棋盘若不存在特殊方格,将该子棋盘右上角的那个方格覆盖为特殊方格...右下的子棋盘若不存在特殊方格,将该子棋盘左上角的那个方格覆盖为特殊方格 至此,每个小棋盘都有一个特殊方格,然后递归调用,就可以解决问题了。...由于覆盖2k*2k的棋盘所需的骨牌个数为(4k-1)/3,所以此算法是一个渐进意义下最优算法。

1.8K110
您找到你想要的搜索结果了吗?
是的
没有找到

Qt中国象棋二——棋盘与棋子的绘制

上次和大家分享了Qt的2D绘图基础知识,这样可以更好地理解象棋中一些关于绘图的程序。这次要和大家分享的则是棋盘与棋子的绘制,也可以说是Qt 2D绘图的一些具体应用。...一、 绘制棋盘 主窗体是继承MainWidget的,将棋盘设置为背景图片,到这棋盘就绘制好了。惊喜吧~ ?...绘制程序也很少: //窗口以棋盘图片为大小 QPixmap pixChessBoard(":/image/Resources/image/chessBoard.png"); setFixedSize...,对应下图中1到2的像素距离 ② RECT_HEIGHT 棋盘图片方格的像素高度,对应下图中2到3的像素距离 ③ 35,45 是棋盘左上角像素坐标,即与1对应 ④ START_X,START_Y 计算棋子位置的起点像素坐标...绘制棋子 ①从图片中切割棋子 资源文件中棋子是这样的,通过drawPixmap(rcTarget,m_itemImage,rcSrc)函数将图片中指定的像素区域切割出来,然后绘制到棋盘上的目标区域,最后就看到棋盘上有棋子的效果了

1K30

分治(详解残缺棋盘 —— Java代码实现

,yk) // 将各子问题的解合并为原问题的解 } } 案例 覆盖残缺棋盘 在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。...其中一个是 4 × 4 缺陷棋盘 [hipg0igymd.png] 在其他三个 4 × 4 棋盘都都相邻的拐角上放一个三格板,使它们也成为缺陷棋盘 递归地覆盖四个4×4缺陷棋盘 在其它三个 4 × 4...棋盘都相邻的拐角上放一个三格板,使它们也成为缺陷棋盘。...[q034wbjx6y.jpeg] Java代码实现 package Chess; public class Chess { // 表示棋盘 private int[][] board; //...* @param tc:棋盘左上角方格的列号 * @param dr:特殊方格所在的行号 * @param dc:特殊棋盘所在的列号 * @param size:2^k, 棋盘的规格为

785107

棋盘覆盖问题(Java

棋盘覆盖问题(Java) 1、问题描述 2、算法设计思路 3、代码实现 4、复杂度分析 5、参考 ---- ---- 1、问题描述 在一个2k×2k个方格组成的棋盘中,若恰有一个方格与其他方格不同,...则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘。...显然特殊方格在棋盘上出现的位置有4k 种情形.因而对任何k ≥ 0,有4k种不同的特殊棋盘。如下图中的特殊棋盘是当k = 2时16个特殊棋盘中的一个。...3、代码实现 ❝特殊棋盘我们采用0来表示,同时假设特殊方格的位置为第三行第三列 ❞ 棋盘一分为四之后,依次覆盖左上角子棋盘、右上角子棋盘、左下角子棋盘、右下角子棋盘。...如若特殊方格在子棋盘中,则递归执行该子棋盘的操作;若不在,对于左上角子棋盘、右上角子棋盘、左下角子棋盘、右下角子棋盘而言,用编号为t的L型骨牌依次覆盖右下角、左下角、右上角、左上角的方格。

72420

保存象棋棋盘信息,需要多少比特?我只用139-167位二进制

例如上述编码对应的哈夫曼树就是: 图片 对于象棋的启发 回到象棋棋盘状态的问题: 将帅有10个位置(包括死亡状态)。 士有6个位置(包括死亡状态)。 象有8个位置(包括死亡状态)。...有办法实现吗? 上面说的很理想,如何实现呢? 我们以10个位置的情况,来探讨通用的编码生成方法。...我在开发《象棋》时,期望通过URL来分享棋局。我希望分享的URL能永久有效,而且不喜欢给服务器太多债务(不采用token+数据库存储棋盘信息)。那么URL中必须包含完整的棋盘信息。...保存历史记录,也是通过类似的手段实现的,占用空间非常小(长度两百的字符串,足够存储大部分常规对局的历史记录)。...欢迎观看 【可以「旋转棋盘」的联机象棋】 - 哔哩哔哩 写在最后 我是HullQin,公众号线下聚会游戏的作者(欢迎关注我,交个朋友)。转发本文前需获得作者HullQin授权。

3.9K111

单标签实现复杂的棋盘布局

最近,有群友问我,他们的一个作业,尽量使用少的标签去实现这样一个象棋布局: 他用了 60 多个标签,而他的同学,只用了 6 个,问我有没有办法尽可能的做到利用更少的标签去完成这个布局效果。...使用渐变实现网格 OK,首先,我们实现最简单的网格布局: 不考虑最外层的一圈边框,我们可以首先利用多重线性渐变实现一个网格布局: .g-grid...background-position: 0 0, 0 0; outline: 1px solid #000; outline-offset: 5px; } 这样,一个架子就差不多了: 当然,棋盘中间的一行...calc(50% + 0.5px), transparent calc(50% + 0.5px), transparent 0), // 棋盘上方的虚线...151px 350px, 151px 350px, 151px 350px, 151px 350px; } 嚯,这渐变代码确实复杂了点,但是其实每一块的作用都是很清晰的,这样,我们的棋盘就变成了这样

57210

判断国际象棋棋盘中一个格子的颜色(难度:简单)

一、题目 给你一个坐标 coordinates ,它是一个字符串,表示国际象棋棋盘中一个格子的坐标。下图是国际象棋棋盘示意图。...给定坐标一定代表国际象棋棋盘上一个存在的格子。坐标第一个字符是字母,第二个字符是数字。...2.2> 示例 2: 【输入】coordinates = "h3" 【输出】true 【解释】如上图棋盘所示,"h3" 坐标的格子是白色的,所以返回 true 。...,我们可以针对 行 和 列 ,做出如下假设性的拆分操作: 【棋盘中列的假设】:a列白色、b列黑色、c列白色、d列黑色…… 【棋盘中行的假设】:1行黑色、2行白色、3行黑色、4行白色…… 然后,我们再观察棋盘中的格子...四、代码实现 4.1> 采用异或方式 class Solution { public boolean squareIsWhite(String coordinates) { // 白色用0表示,

19920

也说棋类游戏

我的连载从2000年4月开始,每个月一次,到10月结束的时候,我会用Java写一个简单的程序来实现对弈。到时候你们可以从我的网站上随便下载,耐心地等吧。   ...一个典型的国际象棋棋盘可以用一个8x8的数组表示,棋盘上的每个格子用一个字节表示——空的格子用0,黑方的王用1,等等。   如今,象棋程序可以在64位计算机上运行了,精心设计的“位棋盘”表示诞生了。...2.着法的产生:同样的道理,抽象层次并不固定着法生成的方法,相应的只是提供了一个抽象接口以便具体层的自行实现,由于程序中采用“黑白棋”作为示例棋类,并且处于简单考虑,所以方法相对简单,仅是生成合法着法。...3.搜索技巧:由于棋类游戏的搜索方法大同小异,所以我在抽象层中便实现了默认的搜索函数代码,但具体层根据需要亦可重载改写,这个默认实现综合运用了一些棋类搜索技巧:例如 散列技术、PVS、期望搜索和MTD(...4.评价局面:同着法产生一样,抽象层留有抽象接口以便具体层可以实现这项功能,示例程序的评价局面实现非常简单,仅是统计棋子数目而已。

76420

算法-经典趣题-舍罕王赏麦

传说国际象棋的发明者是古印度的西萨·班·达依尔。那时的国王是舍罕,世人称为舍罕王。当时舍罕王比较贪玩,位居宰相的西萨·班·达依尔便发明了国际象棋献给舍罕王。...西萨·班·达依尔灵机一动,指着8×8=64的棋盘说:“陛下,请您按棋盘的格子赏赐我一点麦子吧,第1个小格赏我一粒麦子,第2个小格赏我两粒,第3个小格赏四粒,以后每一小格都比前一个小格赏的麦粒数增加一倍,...只要把棋盘上全部64个小格按这样的方法得到的麦粒都赏赐给我,我就心满意足了。”...二、分析 我们来分析下这个问题,国际象棋棋盘总共有8×8=64格。按照西萨·班·达依尔的要求,每一格中放置的麦粒数量如下。...如果使用数学的语言来描述,上述式子可以表述为如下形式: 三、编程 package com.joshua317; import java.util.Scanner; public class Main

67720

不只是围棋!AlphaGo Zero之后DeepMind推出泛化强化学习算法AlphaZero

国际象棋随后成为了一代人工智能研究者努力希望克服的挑战,最终,我们也实现了超越人类水平的国际象棋程序。然而,这些程序高度局限于它们所处的领域,在没有人类大幅度修改的情况下,无法被泛化去处理其他任务。...在本论文中,DeepMind 实现了类似但完全泛化的算法(fully generic algorithm)——在未输入游戏规则以外任何知识的情况下,其推出的全新算法 AlphaZero 在国际象棋和日本将棋上实现了和围棋同样的高水平...在计算复杂性方面,日本将棋(Shogi)要比国际象棋复杂得多:前者有一个更大的棋盘,任何被吃的棋子都可以改变阵营重新上场,被放置在棋盘的大多数位置。...这些规则包含了远程互动(例如,后可以一步穿越整个棋盘,从远距离对王将军)。国际象棋的动作空间包含两名棋手棋盘上棋子的所有合法落子位置;而日本将棋甚至还允许被吃掉的棋子重返棋盘(加入另一方)。...其次,在 MCTS(蒙特卡罗树搜索)中,在神经网络进行评估之前使用随机选择的旋转或反射转换棋盘局势,以使蒙特卡罗评估在不同的偏差中进行平均。象棋和将棋的规则是不对称的,且通常无法假设对称。

68460

动态规划之回溯法(马踏棋盘

需求来源:4399之马踏棋盘小游戏:http://www.4399.com/flash/146267_2.htm 游戏规则:将国际象棋马放入一个6x6的棋盘中,随机指定一个初始位置,求棋子走完棋盘的步法...解题思路:二维数组模拟棋盘,记录其步数,再使用一个boolean型的二维数组模拟棋盘,判断其位置是否已经走过                 使用Java的Point类表示棋子,根据国际象棋马儿的走法可知一个棋子最多有...) 算法思想:动态规划算法之回溯法 优化思想:贪心算法减少回溯次数 代码实现:(回溯法) import java.awt.Point; import java.util.LinkedList; /**...long time = (end - start)/1000; System.out.println("一共耗时: "+ time + " 秒"); } /** * 核心算法,回溯实现...; import java.util.Comparator; import java.util.LinkedList; /** * 马踏棋盘算法 * 回溯法、贪心算法 * @author com

1.4K20
领券