棋盘覆盖问题（分治法）使用JavaScript可视化！

2022-11-28 20:32:09

棋盘覆盖问题（分治法）

1.问题描述

问题：在一个2^k*2^k（k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。

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

2.算法分析

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

3.关键代码

3.1使用的编程语言及程序使用说明

本算法演示采用JavaScript实现逻辑和HTML、CSS可视化显示。

打开iteml1.html的文件（使用浏览器，推荐chorme）如图所示：

3.2关键代码

//分治法处理棋盘矩阵
chessBoard:function(tr,tc,dr,dc,size){
    var s,t;
    if (size == 1) return;
    s =size/2;
    t = ++this.nCount ;
    if (dr < tr + s && dc < tc +s)
        this.chessBoard(tr,tc,dr,dc,s);
    else
    {
        this.Matrix[tr+s-1][tc+s-1] = t;
        this.chessBoard(tr,tc,tr+s-1,tc+s-1,s);
    }
    if (dr < tr + s && dc >= tc + s )
        this.chessBoard(tr,tc+s,dr,dc,s);
    else
    {
        this.Matrix[tr+s-1][tc+s] = t;
        this.chessBoard(tr,tc+s,tr+s-1,tc+s,s);
    }
    if (dr >= tr + s && dc < tc + s)
        this.chessBoard(tr+s,tc,dr,dc,s); 
    else
    {
        this.Matrix[tr+s][tc+s-1] = t;
        this.chessBoard(tr+s,tc,tr+s,tc+s-1,s);
    }
    if (dr >= tr + s && dc >= tc + s)
        this.chessBoard(tr+s,tc+s,dr,dc,s);
    else
    {
        this.Matrix[tr+s][tc+s] = t;
        this.chessBoard(tr+s,tc+s,tr+s,tc+s,s);
    }
}

4.效果验证

边长为4的棋盘，特殊方格所在坐标为（2，3）
边长为8的棋盘，特殊方格所在坐标为（7，3）
边长为16的棋盘，特殊方格所在坐标为（7，13）

项目地址：（欢迎白嫖！）：

https://github.com/DuoRouLongShu/AlgorithmItems.git

码农公寓