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

棋盘覆盖问题

Tags: 算法 棋盘覆盖问题 ---- 【问题描述】 在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有...k = 3,棋盘大小8 x 8 在棋盘覆盖问题中,要用下图中 4 中不同形态的** L 型骨牌覆盖一个给定的特殊棋牌上除特殊方格以外的所有方格,且任何 2 个 L 型骨牌不得重叠覆盖**。...为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘,我们可以用一个 L 型骨牌覆盖这 3 个较小的棋盘的汇合处,如下图所示,这 3 个子棋盘上被 L 型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而将原问题化为...4 个较小规模的棋盘覆盖问题。...【C语言代码】 #include #define BOARD_SIZE 4 int board[BOARD_SIZE][BOARD_SIZE]; // c1, r1: 棋盘左上角的行号和列号

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

    棋盘覆盖问题(Java)

    棋盘覆盖问题中,要用下图所示的4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。...易知,在任何一个2k×2k的棋盘覆盖中,用到的L型骨牌个数恰好为(4k - 1)/3。 2、算法设计思路 使用分治策略,可以设计出解棋盘覆盖问题的简洁算法。...为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如下图(b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题。...3、代码实现 ❝特殊棋盘我们采用0来表示,同时假设特殊方格的位置为第三行第三列 ❞ 棋盘一分为四之后,依次覆盖左上角子棋盘、右上角子棋盘、左下角子棋盘、右下角子棋盘。...覆盖其余棋盘方格 ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s); } // TODO 2.覆盖右上角子棋盘

    76520

    棋盘覆盖问题(转载)

    问题描述 在一个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。

    54310

    java 实现棋盘覆盖问题

    问题描述:在一个2k*2k的棋盘中,有一个特殊方格,要求用L型骨牌覆盖满除特殊方格外的所有其他方格,且骨牌不得重叠....: 左上的子棋盘若不存在特殊方格,将该子棋盘右下角的那个方格覆盖为特殊方格 右上的子棋盘若不存在特殊方格,将该子棋盘左下角的那个方格覆盖为特殊方格 左下的子棋盘若不存在特殊方格,将该子棋盘右上角的那个方格覆盖为特殊方格...右下的子棋盘若不存在特殊方格,将该子棋盘左上角的那个方格覆盖为特殊方格 至此,每个小棋盘都有一个特殊方格,然后递归调用,就可以解决问题了。... board;  /** 模拟骨牌(相同数字为同一块骨牌)  */  static int tile = 1;  /**   * 棋盘覆盖问题   * @param dr  左上角方格行号   * @...由于覆盖2k*2k的棋盘所需的骨牌个数为(4k-1)/3,所以此算法是一个渐进意义下最优算法。

    1.8K110

    递归与分治之棋盘覆盖问题

    在一个2^k * 2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘。...显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k≥0,有4^k种不同的特殊棋盘。 下图所示的特殊棋盘为 k=2 时 16 个特殊棋盘中的一个。 ?...在棋盘覆盖问题中,要用下图中 4 中不同形态的 L 型骨牌覆盖一个给定的特殊棋牌上除特殊方格以外的所有方格,且任何 2 个 L 型骨牌不得重叠覆盖。 ?...当 k>0 时,将 2^k * 2^k 棋盘分割为 4 个 2^(k-1) * 2^(k-1) 子棋盘,如下图所示。 ? 特殊方格必位于 4 个子棋盘之一,其余 3 个子棋盘中无特殊方格。...用一个 L 型骨牌覆盖这 3 个较小的棋盘的汇合处,如图所示,将这 3 个无特殊方格的子棋盘转化为特殊棋盘,从而将原问题化为 4 个较小规模的棋盘覆盖问题。

    1.3K60

    语言跳出循环 c,易语言教程循环控制(到循环尾和跳出循环)

    到循环尾()和跳出循环()是易语言对循环的两种控制方式,教程分别了举例师范讲解。...操作系统需求: Windows、Linux、Unix 跳出循环 调用格式: 〈无返回值〉 跳出循环 () – 系统核心支持库->流程控制 英文名称:break 本命令转移当前程序执行位置到当前所处循环体循环尾语句的下一条语句处...整数型 .判断循环首 (m < 10) m = m + 1 .如果真 (m = 5) 到循环尾 () .如果真结束 画板1.滚动写行 (m) .判断循环尾 () .子程序 _按钮2_被单击, , , 跳出循环....局部变量 m, 整数型 .判断循环首 (m < 10) m = m + 1 .如果真 (m = 8) 跳出循环 () .如果真结束 画板1.滚动写行 (m) .判断循环尾 () 画板1.写出 (“m...=” + 到文本 (m) + “跳出循环”) .子程序 _按钮3_被单击, , , 奇数 .局部变量 n, 整数型 .’

    6.5K20
    领券