专栏首页技术碎碎念递归与分治之棋盘覆盖问题

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

在一个2^k * 2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘。

显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k≥0,有4^k种不同的特殊棋盘。

下图所示的特殊棋盘为 k=2 时 16 个特殊棋盘中的一个。

在棋盘覆盖问题中,要用下图中 4 中不同形态的 L 型骨牌覆盖一个给定的特殊棋牌上除特殊方格以外的所有方格,且任何 2 个 L 型骨牌不得重叠覆盖。

易知,在任何一个 2^k * 2^k 的棋盘中,用到的 L 型骨牌个数恰为 (4^k-1)/3 。

求解棋盘问题,可利用分治的策略。当 k>0 时,将 2^k * 2^k 棋盘分割为 4 个 2^(k-1) * 2^(k-1) 子棋盘,如下图所示。

特殊方格必位于 4 个子棋盘之一,其余 3 个子棋盘中无特殊方格。用一个 L 型骨牌覆盖这 3 个较小的棋盘的汇合处,如图所示,将这 3 个无特殊方格的子棋盘转化为特殊棋盘,从而将原问题化为 4 个较小规模的棋盘覆盖问题。递归的使用 这种分割,直至棋盘简化为 1x1 棋盘。

python实现代码如下:

 1 # coding =gbk
 2 
 3 
 4 # tr左上角行号,tc左上角列号。dr特殊方格行号,dc特殊方格列号
 5 def chessboard(board, size, tr, tc, dr, dc):
 6     if size <= 1:
 7         return
 8     global tile
 9     tile += 1
10     current_tile = tile
11     size //= 2
12     if dr < tr + size and dc < tc + size:
13         chessboard(board, size, tr, tc, dr, dc)
14     else:
15         board[tr + size - 1][tc + size - 1] = current_tile
16         chessboard(board, size, tr, tc, tr + size - 1, tc + size - 1)
17     if dr >= tr + size and dc < tc + size:
18         chessboard(board, size, tr + size, tc, dr, dc)
19     else:
20         board[tr + size][tc + size - 1] = current_tile
21         chessboard(board, size, tr + size, tc,
22                    tr + size, tc + size - 1)
23     if dr < tr + size and dc >= tc + size:
24         chessboard(board, size, tr, tc + size, dr, dc)
25     else:
26         board[tr + size - 1][tc + size] = current_tile
27         chessboard(board, size, tr, tc + size,
28                    tr + size - 1, tc + size)
29     if dr >= tr + size and dc >= tc + size:
30         chessboard(board, size, tr + size, tc + size, dr, dc)
31     else:
32         board[tr + size][tc + size] = current_tile
33         chessboard(board, size, tr + size, tc + size,
34                    tr + size, tc + size)
35 
36 
37 tile = 0
38 chessboard_size = 4
39 board = [[0 for x in range(chessboard_size)] for y in range(chessboard_size)]
40 chessboard(board, chessboard_size, 0, 0, 1, 0)
41 
42 board = [[row[i] for row in board] for i in range(len(board[0]))]
43 for lst in board:
44     print(lst)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构之链表、栈和队列 java代码实现

    定义抽象节点类Node: 1 package cn.wzbrilliant.datastructure; 2 3 /** 4 * 节点 5 * ...

    欠扁的小篮子
  • Jsp语法、指令及动作元素

    一、JSP的语法 1、JSP的模板元素:(先写HTML)    就是JSP中的那些HTML标记    作用:页面布局和美化 2、JSP的Java脚本表达式:  ...

    欠扁的小篮子
  • BigDecimal精度与相等比较的坑

    欠扁的小篮子
  • C语言中size_t和size_type 的区别

    1)size_tsize_t是用于数组的下标值类型,也可以用来“接收”sizeof操作符的返回值。

    ccf19881030
  • 短视频商城源码,制作彩色验证码

    yunbaokeji柯基
  • [开发技巧]·AdaptivePooling与Max/AvgPooling相互转换

    自适应池化Adaptive Pooling是PyTorch的一种池化层,根据1D,2D,3D以及Max与Avg可分为六种形式。

    小宋是呢
  • C 库函数 - fread()

    C 库函数 size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream) 从给定流 stre...

    心跳包
  • JS的函数调用栈有多深?

    译者按: 有时候会遇到 Maximum call stack size exceeded 的问题,本文教你 stack size 的计算方法。

    Fundebug
  • pytorch之Resize()函数具体使用详解

    CLASS torchvision.transforms.Resize(size, interpolation=2)

    砸漏
  • 880.Decoded String at Index

    思路 用size表示在i处,字符串进行解码后的长度。 如果有一个解码后的字符串为appleappleappleappleappleapple,且K=24,那...

    平凡的学生族

扫码关注云+社区

领取腾讯云代金券