算法 - 棋盘覆盖（JavaScript）

我就是我 2023-09-28 19:04 21阅读 0赞

**目录**

题目描述

输入

输出

题目解析

算法代码实现

--------------------

### 题目描述 ###

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

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

![706f792e2d9f454390f9a561758534b0.png][]

### 输入 ###

控制台输入

第一行为整数k，（不是棋盘大小是2^k \* 2^k，1≤k≤10），

第二行是两个整数，表示特殊方格所在行和列。

> 3
> 
> 2 2

### 输出 ###

特殊方格用0表示，数据间用制表符隔开，要求遍历顺序按从左到右，从上到下。具体看样例

> 3 3 4 4 8 8 9 9  
> 3 0 2 4 8 7 7 9  
> 5 2 2 6 10 10 7 11  
> 5 5 6 6 1 10 11 11  
> 13 13 14 1 1 18 19 19  
> 13 12 14 14 18 18 17 19  
> 15 12 12 16 20 17 17 21  
> 15 15 16 16 20 20 21 21

### 题目解析 ###

输入

> 3
> 
> 2 2

表示创建一个2³ x 2³ 的棋盘，即 8 x 8 棋盘，该棋盘中有一个特殊方格，其位置在棋盘的第2行，第2列。

按照题目要求，我们可以使用4种不同形态的L型骨牌来覆盖特殊方格(2,2)其外的其他方格，L型骨牌可以用相同的数字来标记，如下图所示：

![c8cf0819296140e3ab0c1b0f4e5ae520.png][]

此题的解题思路采用分治法

假设k=1，则此时棋盘为2x2网格

![b5748d6004fb46e9afb86fabd8607533.png][]

特殊方格0的位置共有四处可能，如上图所示，

而无论特殊方格位置在哪，我们都可以使用不同形态的L型骨牌填充剩余格子

--------------------

假设k=2，此时棋盘为4x4网格

特殊方格的放置位置可以有16处，但是特殊方格无论怎么放置，都可以转化如下四种位置（代入旋转，镜像，反转思维看）

![89bc2c88cf984da08ebdf4c3a7a04e35.png][]

因此，我们将4x4棋盘，分解为了4个2x2子棋盘，则特殊方格可以放置在任意一个2x2子棋盘中，并且放置在子棋盘中的位置只有上图所示的四种情况。

则此时，特殊方格所在的子棋盘的剩余网格必然可以被L型骨牌覆盖，如下图所示：

![6ab8c1194626441aaf36e35e91794c8e.png][]

剩下工作就是将剩余的3个2x2的子棋盘用L型骨牌覆盖：

我们已经知道了一个L型骨牌占据三个方格，因此一个2x2的棋盘只能放入一个L型骨牌，并且还剩1个空闲方格。

因此3个2x2棋盘可以放3个L型骨牌，还剩余3个空闲方格。而剩余的3个空闲方格数目刚好符合一个L型骨牌所需要占据的方格数。

因此，我们必须让3个2x2棋盘放完L型骨牌后产生的空闲方格紧挨在一起，这样才能再次凑出一个L型骨牌。

反过来思考，我们可以先将剩余的3个2x2子棋盘的空闲网格位置先确定了，让3个空闲网格形成L型骨牌

![6a79301f482e4b43b8526b45de53048e.png][]

因此最终4x4棋盘的覆盖策略如下：

![a121ad2ae72f484aaa51df0fac86b55c.png][]

为了保证分治法分解出来的子问题是相同的，我们可以将空闲网格也看成特殊方格。

--------------------

假设k=3，则此时棋盘为8 x 8的网格

按照之前的思路，我们需要将：

8x8的棋盘，分解为 4个 4x4 的棋盘，则特殊方格0必然在某个4x4棋盘中。

假设，我们找到了包含特殊方格的4x4棋盘，则我们需要继续将4x4棋盘分解为4个 2x2 棋盘，同样的，特殊方格0必然在某个2x2棋盘中。

假设，我们找到了包含特殊方格的2x2棋盘，我们称此2x2棋盘为a棋盘，则a棋盘的覆盖策略已经确定，如下图橙色L型骨牌覆盖。

另外3个2x2棋盘的空闲网格位置也被迫确定了，如下图绿色L型骨牌覆盖。

而3个2x2棋盘的空闲网格位置确定好了，则它们的L型骨牌覆盖策略也就定了。

![92920bdd48a64050b339a418b40cf03f.png][]![23039e14661e45378a71482b0fe8c867.png][]

因此一个4x4棋盘的覆盖策略就被确定了，我们称此4x4棋盘为A棋盘。

通过A棋盘的覆盖，我们发现，一个 2^k \* 2^k 的棋盘，放下足够多的L型骨牌后，必然还剩一个空闲网格。比如2x2棋盘只能放下 2x2/3=1...1个，4x4棋盘只能放下4x4/3=5...1，8x8棋盘只能放下8x8/3=21...1。

因此8x8棋盘中除了A棋盘外的剩余3个4x4子棋盘，无论每个4x4棋盘如何放置L型骨牌，自身必然剩余1个空闲网格。则3个4x4棋盘必然还剩3个空闲网格，则此时我们只能将这三个空闲网格凑在一起，形成L型骨牌。

![dee04a96956e426b919eeb96bf588d01.png][]

同样地，为了保证分治法分解出来的子问题是相同的，我们可以将空闲网格也看成特殊方格。

因此本题的分解思路应该如下：

*  将2^k \* 2^k棋盘分为4个 2^(k-1) \* 2^(k-1)的子棋盘，判断特殊方格位于哪个子棋盘中

1.  含有特殊方格的子棋盘继续进行分解，直到子棋盘为1x1
2.  不含有特殊方格的子棋盘，我们人为的为其设定一个特殊方格，即指定它们的空闲方格的为特殊方格。而它们空闲方格的位置，必然是相连的且围绕（含有特殊方格的子棋盘），如下图所示：
3.  ![5063eb3431c946a8820551fcc9836ab6.png][]

### 算法代码实现 ###

/* JavaScript Node ACM模式 控制台输入获取 */
    const readline = require("readline");
    
    const rl = readline.createInterface({
      input: process.stdin,
      output: process.stdout,
    });
    
    const arr = [];
    rl.on("line", (line) => {
      arr.push(line);
      if (arr.length === 2) { // 让控制台支持多行输入
        const k = parseInt(arr[0]);
        const [r, c] = arr[1].split(" ").map((item) => parseInt(item));
    
        gridCover(k, r, c).map((row) => {
          console.log(row.join("\t"));
        });
    
        arr.length = 0; // 让控制台支持不断输入测试
      }
    });
    
    /* 棋盘覆盖 */
    function gridCover(k, row, col) {
      // tile是L型骨牌的编号
      let tile = 1;
      // 棋盘大小 size x size，而size = 2^k
      let size = 1 << k;
    
      // 创建一个size x size大小的二维数组作为棋盘
      const grid = createGrid(size, size);
      // 标记出特殊方格的位置
      grid[row - 1][col - 1] = 0;
    
      // tr表示棋盘左上角的行号，tc表示棋盘左上角的列号，dr表示特殊方格的行号，dc表示特殊方格的列好，size表示棋盘的大小
      function chessBoard(tr, tc, dr, dc, size) {
        if (size === 1) return;
    
        let t = tile++;
        let s = size / 2;
    
        // 如果特殊方格0位于左上角子棋盘中，则左上角子棋盘为特殊棋盘
        if (dr < tr + s && dc < tc + s) {
          // 分解特殊棋盘
          chessBoard(tr, tc, dr, dc, s);
        } else {
          // 否则，左上角子棋盘不是特殊棋盘，我们可以将其空闲方格位置（右下角）定义为特殊方格，让其变为一个特殊棋盘
          grid[tr + s - 1][tc + s - 1] = t;
          // 分解特殊棋盘
          chessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
        }
    
        // 如果特殊方格0位于右上角子棋盘中，则右上角子棋盘为特殊棋盘
        if (dr < tr + s && dc >= tc + s) {
          // 分解特殊棋盘
          chessBoard(tr, tc + s, dr, dc, s);
        } else {
          // 否则，右上角子棋盘不是特殊棋盘，我们可以将其空闲方格位置（左下角）定义为特殊方格，让其变为一个特殊棋盘
          grid[tr + s - 1][tc + s] = t;
          chessBoard(tr, tc + s, tr + s - 1, tc + s, s);
        }
    
        // 如果特殊方格0位于左下角子棋盘中，则左下角子棋盘为特殊棋盘
        if (dr >= tr + s && dc < tc + s) {
          // 分解特殊棋盘
          chessBoard(tr + s, tc, dr, dc, s);
        } else {
          // 否则，左下角子棋盘不是特殊棋盘，我们可以将其空闲方格位置（右上角）定义为特殊方格，让其变为一个特殊棋盘
          grid[tr + s][tc + s - 1] = t;
          chessBoard(tr + s, tc, tr + s, tc + s - 1, s);
        }
    
        // 如果特殊方格0位于右下角子棋盘中，则右下角子棋盘为特殊棋盘
        if (dr >= tr + s && dc >= tc + s) {
          // 分解特殊棋盘
          chessBoard(tr + s, tc + s, dr, dc, s);
        } else {
          // 否则，右下角子棋盘不是特殊棋盘，我们可以将其空闲方格位置（左上角）定义为特殊方格，让其变为一个特殊棋盘
          grid[tr + s][tc + s] = t;
          chessBoard(tr + s, tc + s, tr + s, tc + s, s);
        }
      }
    
      chessBoard(0, 0, row - 1, col - 1, size);
      return grid;
    }
    
    /* 创建二维数组 */
    function createGrid(row, col) {
      const grid = new Array(row);
      for (let i = 0; i < row; i++) {
        grid[i] = new Array(col);
      }
      return grid;
    }

![7932be82ae014475add509b17171c544.png][]

在写算法过程中，遇到的比较棘手的问题就是JavaScript创建二维数组。

我们不能使用 const 2dArr = new Array(8).fill(new Array(8))来创建二维数组，因为数组的fill方法会用入参填充数组元素。如果fill入参是一个对象，则被填充的数组的所有元素都指向该对象。

所以我们只能老老实实的for循环去创建。

另外 new Array(8)表示创建一个长度为8的数组，但是此时数组元素都是empty。

而当数组元素是empty时，数组原型上的一些方法，如forEach、map、filter、some、every、reduce将会跳过这些empty元素，所谓跳过，即这些empty元素不会进入callback回调。这是稀疏数组特性。

[706f792e2d9f454390f9a561758534b0.png]: https://img-blog.csdnimg.cn/706f792e2d9f454390f9a561758534b0.png
[c8cf0819296140e3ab0c1b0f4e5ae520.png]: https://img-blog.csdnimg.cn/c8cf0819296140e3ab0c1b0f4e5ae520.png
[b5748d6004fb46e9afb86fabd8607533.png]: https://img-blog.csdnimg.cn/b5748d6004fb46e9afb86fabd8607533.png
[89bc2c88cf984da08ebdf4c3a7a04e35.png]: https://img-blog.csdnimg.cn/89bc2c88cf984da08ebdf4c3a7a04e35.png
[6ab8c1194626441aaf36e35e91794c8e.png]: https://img-blog.csdnimg.cn/6ab8c1194626441aaf36e35e91794c8e.png
[6a79301f482e4b43b8526b45de53048e.png]: https://img-blog.csdnimg.cn/6a79301f482e4b43b8526b45de53048e.png
[a121ad2ae72f484aaa51df0fac86b55c.png]: https://img-blog.csdnimg.cn/a121ad2ae72f484aaa51df0fac86b55c.png
[92920bdd48a64050b339a418b40cf03f.png]: https://img-blog.csdnimg.cn/92920bdd48a64050b339a418b40cf03f.png
[23039e14661e45378a71482b0fe8c867.png]: https://img-blog.csdnimg.cn/23039e14661e45378a71482b0fe8c867.png
[dee04a96956e426b919eeb96bf588d01.png]: https://img-blog.csdnimg.cn/dee04a96956e426b919eeb96bf588d01.png
[5063eb3431c946a8820551fcc9836ab6.png]: https://img-blog.csdnimg.cn/5063eb3431c946a8820551fcc9836ab6.png
[7932be82ae014475add509b17171c544.png]: https://img-blog.csdnimg.cn/7932be82ae014475add509b17171c544.png