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

棋盘覆盖问题(Java

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

76520

java 实现棋盘覆盖问题

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

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

    分治(详解残缺棋盘 —— 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, 棋盘的规格为

    839107

    棋盘分割

    作者 | 小K 出品 | 公众号:小K算法 01 故事起源 有一个8*8的棋盘,沿着格子的边进行分割,每分割一块拿走,将剩下的矩形棋盘继续分割。 n-1次分割后,可以得到n块矩形棋盘。...假设原棋盘每一格都有一个分值,则分割后的每一块都有一个总分,总分即为所有格子分值之和。 设分割的每一块棋盘总分为xi。 如何分割可以让各矩形棋盘总分的均方差最小?...例如一个4*4的棋盘,先垂直切,就可以从3个不同的位置切。 如果给棋盘加一个坐标,每一种切法就可以用一个线段来具体表示,比如用这条切线的两个端点坐标。...分割之后,就变成了2个更小的棋盘,而这2个棋盘也可以用矩形的坐标表示,此时就把原问题变成了子问题,原问题的最优解也就是所有子问题中选一个最优的。...初始化的时候,所有小块的独立矩形棋盘都一次不切,所以就是矩形棋盘的分值平方。

    63220

    【题解】棋盘

    [NOIP2017 普及组] 棋盘 题目背景 NOIP2017 普及组 T3 题目描述 有一个m×mm \times mm×m的棋盘棋盘上每一个格子可能是红色、黄色或没有任何颜色的。...你现在要从棋盘的最左上角走到棋盘的最右下角。 任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的), 你只能向上、 下、左、 右四个方向前进。...现在你要从棋盘的最左上角,走到棋盘的最右下角,求花费的最少金币是多少? 输入格式 第一行包含两个正整数m,nm, nm,n,以一个空格分开,分别代表棋盘的大小,棋盘上有颜色的格子的数量。...棋盘左上角的坐标为(1,1)(1, 1)(1,1),右下角的坐标为(m,m)(m, m)(m,m)。 棋盘上其余的格子都是无色。...保证棋盘的左上角,也就是(1,1)(1, 1)(1,1) 一定是有颜色的。 输出格式 一个整数,表示花费的金币的最小值,如果无法到达,输出−1-1−1。

    1.7K20

    Spread表格组件For JAVA功能介绍—表格相关操作

    之前有篇文章我们说到 Spread 表格组件的 Java CTP 版本已经发布:《表格组件JAVACTP版本抢先预览》。....setValue("Total Monthly Income"); worksheet.getRange("E7").setValue("Total Monthly Expenses"); 4.创建表格...TableStyleMedium4"));incomeTable.setTableStyle(workbook.getTableStyles().get("TableStyleMedium4")); 5.设置表格公式...FileOutputStream(f); workbook.save(out); out.close(); 大功告成,让我们打开导出的Excel看一下效果: 以上就是 Spread Service 在java...平台表格相关的功能示例,相信看了之后大家对 Spread Service的表格应用会有一些收获,除此之外,Spread表格组件还有许多强大的功能,有兴趣的朋友可以免费试用本产品。

    1.2K30

    棋盘覆盖问题

    Tags: 算法 棋盘覆盖问题 ---- 【问题描述】 在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有...四个子棋盘 特殊方格必位于 4 个较小子棋盘之一中,其余 3 个子棋盘中无特殊方格。...为了在递归处理的过程中使用同一个棋盘,将数组board设为全局变量; (2)子棋盘:整个棋盘用二维数组board[size][size]表示,其中的子棋盘棋盘左上角的下标tr、tc和棋盘大小s表示;...<<endl; } cout<<endl; } int main() { test(); return 0; } 【JAVA...此类的源代码如下: package com.qipan.test; import java.awt.Color; import java.awt.GridLayout; import java.util.Random

    3.2K100

    java表格识别PaddleOcr总结

    简单总结下前面写了些借助opencv实现表格的一些方法,但是内容识别我是用的paddleocr(我只是切割后识别,但是paddleocr其实识别结果是自带坐标的也就是说直接有表格识别的能力,但是这东西吧不能通用有些遇到问题还是需要个性化处理下...如果是c++、python的话就可以直接开搞了,但是其他语言例如用java需要动态库,本篇简单说下dll代码吧(提前说下因为我碰到C++懵逼了,第一次我想到的是结果json序列化但是那个包引入有点麻烦我放弃了...java里面声明也很简单,但是注意属性应该用public不然参数指定顺序会报错的。...读光表格模型读光表格分为有线和无线,如果用python的可以试下。...网上应该是作者出了个onnx的版本,这个导出的模型没有默认长和宽这个需要注意下,另外模型转onnx后运算处理逻辑还是太复杂了(主要一些数学函数处理)java没有这方面的类库不好处理也试着用AI翻译下但还是放弃了

    11710

    棋盘覆盖问题(转载)

    问题描述 在一个2^k×2^k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。...在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 ? ?...解题思路 分析:当k>0时,将2k×2k棋盘分割为4个2^k-1×2^k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格。...为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如 (b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为棋盘1×1。

    54210

    Java 操作excel表格 - JXL(Java excel api)

    Java 操作excel表格 Java 操作 Excel 最常用的就是JXL(Java excel api)和POI,用起来挺简单的,不过相应的其功能也并非很强大,够用就行!...首先,下载jxl.jar 文件,点我下载 其次,将jxl.jar导入项目 操作步骤:鼠标选中项目右击 =》 最后一项(Properties) => 选择第三项(Java Build Path) => 选择第三项...还有很多 ---- 示例效果图 示例代码: package com.servlet; import java.io.File; import java.io.FileOutputStream; import...java.io.IOException; import java.io.OutputStream; import java.io.PrintWriter; import javax.servlet.ServletException...request.setCharacterEncoding("UTF-8"); String fname = "院士专家工作站人员动态服务表"; fname = java.net.URLEncoder.encode

    4.2K20
    领券