棋盘覆盖问题与可视化代码演示

站长

2023年09月16日 17:47 · 阅读数 21

前言

棋盘覆盖

今天要做的是一个棋盘覆盖的玩意，这个呢，也是某位老师留的一个小问题，那么这个就让小爷来终结吧~

描述

这个很简单，就是那啥有一个棋盘，然后这个棋盘是 2^k * 2^k 大小的，然后有一个障碍物，现在要你再不覆盖障碍物的情况下，去使用四种骨牌去覆盖棋盘。如下图：棋盘覆盖问题与可视化代码演示

题目就是这个题目，思路也是典型的那个分治。当然那个这个也是说一下这个问题，怎么个分治法，策略是什么。来先看看我们最后实现的效果棋盘覆盖问题与可视化代码演示

思路

说到这个分治，我们必然要用到递归，说到递归我们必然要最起码讨论两种情况，开始和结束状态。搞清楚开始状态有利于编写流程，搞清楚结束状态有利于编写结束位置。

开始

都说了，分治，那么必然是问题划分，分解子问题，对于一个2x2的棋盘，我们只需要考虑阻碍点在哪，然后把走位点覆盖那么就是我们想要的效果，例如这样。

棋盘覆盖问题与可视化代码演示

所以对于一个大棋盘我们要考虑的就是划分呀，把一张大棋盘一直划分，每次划分的时候构建相同的子问题。

子问题构建

问了来了，子问题是啥，子问题就是一个区域内长得像上图的区域，然后在那种区域内求解问题。所以我们怎么干，这样干。

棋盘覆盖问题与可视化代码演示

结束

这个时候我们看到最小问题的情况下（最小子问题），当2x2的时候，我们按照我们的中间过程，我们会打周围的都覆盖，之后再划分，那个时候都变成1x1的格子了，这个时候显然就没有必要继续分割了，退出。

初步编写代码

这次的话是采用python进行编写。因为考虑到那个要那啥图形化嘛，是吧，而且这次也是使用python在一年前提出的新的语法特性来玩玩。这里的话也是现在我们的控制台输出程序。不过这里要注意保存一下我们的那个覆盖的方式。

TIMES = 1 #放置的次数

ROUTERS = dict()

def showBord(bord:list):
    for rows in bord:
        for j in rows:
            print(j,end=" ")
        print("")


def AddRouter(key:int,value:tuple):
    global ROUTERS
    if(ROUTERS.get(key)):
        temp = ROUTERS.get(key)
        temp.append(value)
    else:
        ROUTERS[key] = list()
        temp1 = ROUTERS.get(key)
        temp1.append(value)





def ChessBord(tr:int,tc:int,dr:int,dc:int,size:int,BORD:list):
    global TIMES,ROUTERS
    #不断分割，知道size为1
    if(size == 1):
        return
    T = TIMES #当前覆盖的玩意
    TIMES +=1

    s = int(size/2) #开始做分割

    #开始四个方位去判断那个有木有方格子，没有就继续分割，如果没有那么就在那边标记一下
    #左上角
    if(dr<tr+s and dc<tc+s):
        ChessBord(tr,tc,dr,dc,s,BORD)
    else:
        BORD[tr+s-1][tc+s-1] = T
        AddRouter(T,(tr+s-1,tc+s-1))
        ChessBord(tr,tc,tr+s-1,tc+s-1,s,BORD)

    #右上角
    if (dr < tr + s and dc >= tc + s):
        ChessBord(tr, tc+s, dr, dc, s, BORD)
    else:
        BORD[tr + s - 1][tc + s] = T
        AddRouter(T,(tr + s - 1,tc + s))
        ChessBord(tr, tc+s, tr + s , tc + s - 1, s, BORD)

    #左下角
    if (dr >= tr + s and dc < tc + s):
        ChessBord(tr+s, tc, dr, dc, s, BORD)
    else:
        BORD[tr + s][tc + s - 1] = T
        AddRouter(T,(tr + s,tc + s - 1))
        ChessBord(tr+s, tc, tr + s, tc + s - 1, s, BORD)

    #右下角
    if (dr >= tr + s and dc >= tc + s):
        ChessBord(tr+s, tc+s, dr, dc, s, BORD)
    else:
        BORD[tr + s ][tc + s ] = T
        AddRouter(T,(tr + s ,tc + s ))
        ChessBord(tr + s, tc + s, tr + s, tc + s, s, BORD)


if __name__ == '__main__':

    SIZE = int(input("please input your size (the size must be 2^k："))
    dr = int(input("please input the barrier row"))
    dc = int(input("please input the barrier column"))
    BORD = [[0 for x in range(SIZE)] for i in range(SIZE)]  # 初始化棋盘

    ChessBord(0,0,dr,dc,SIZE,BORD)
    showBord(BORD)
    for i in ROUTERS.keys():
        print(ROUTERS.get(i))

棋盘覆盖问题与可视化代码演示那个0就是我们一开始的障碍物。

图形化升级

接下来要做的就是图像话升级。这个也好办，我这里直接使用海龟绘图

棋盘绘制

from turtle import Turtle

import turtle

Size = 8
turtle.screensize(800,800,"white")

class Board(Turtle):
    def __init__(self,size,dr,dc):

        Turtle.__init__(self)
        self.shape('square')
        self.hideturtle()
        self.speed(30)
        self.width = 600
        self.height = 800
        self.size = size

        self.boxsize = 50

        self.startx = -int((self.size * self.boxsize)/2)
        self.starty = int((self.size * self.boxsize)/2)


        self.rebound()

        self.drawboard() #绘制棋盘
        self.drawfill("red",dr,dc)
        # self.drawfill("aqua",0,5)

    def drawrowline(self):

        for i in range(self.size+1):
            self.pendown()
            self.forward(self.size*self.boxsize)
            self.penup()
            self.goto(self.startx,self.starty-((i+1)*self.boxsize))

        self.rebound()

    def drawcolumnline(self):
        self.right(90) #调换方向
        for i in range(self.size+1):
            self.pendown()
            self.forward(self.boxsize*self.size)
            self.penup()
            self.goto(self.startx+self.boxsize*(i+1),self.starty)
        self.rebound()

    def drawboard(self):
        self.drawrowline()
        self.drawcolumnline()
        self.rebound()

    def move(self,UI_x,UI_y):
        self.penup()
        self.goto(UI_x,UI_y)
    def transforuipos(self,row,column):

        #负责把那个矩阵上面的坐标换算为在UI界面的坐标
        UI_y = (self.starty - row*self.boxsize)
        UI_x = self.startx + self.boxsize*column

        return UI_x,UI_y
    def drawfill(self,color,row,column):
        UI_x,UI_y= self.transforuipos(row,column)
        self.move(UI_x,UI_y)

        #给方格上色
        self.pendown()
        self.begin_fill()
        self.fillcolor(color)
        for i in range(4):
            self.forward(self.boxsize)
            self.right(90)
        self.end_fill()
        self.rebound()

    def rebound(self):
        #复原
        if(self.isdown()):
            self.penup()
        self.home()
        self.goto(self.startx, self.starty)  # 起始点

if __name__ == '__main__':
    board = Board(8,2,2)

    turtle.mainloop()

这里有个坑，那就是那个goto()这个是按照那个中心坐标来算的，刚刚调了小半天，坑死我了。棋盘覆盖问题与可视化代码演示

整合

现在可以开始整合我们的代码了。

整合算法


class Algorithm:
    def __init__(self):
        self.TIMES = 1
        self.ROUTERS = dict()

    def showBordinConsole(self,bord: list):
        for rows in bord:
            for j in rows:
                print(j, end=" ")
            print("")

    def AddRouter(self,key: int, value: tuple):

        if (self.ROUTERS.get(key)):
            temp = self.ROUTERS.get(key)
            temp.append(value)
        else:
            self.ROUTERS[key] = list()
            temp1 = self.ROUTERS.get(key)
            temp1.append(value)

    def ChessBord(self,tr: int, tc: int, dr: int, dc: int, size: int, BORD: list):

        # 不断分割，知道size为1
        if (size == 1):
            return
        T = self.TIMES  # 当前覆盖的玩意
        self.TIMES += 1

        s = int(size / 2)  # 开始做分割

        # 开始四个方位去判断那个有木有方格子，没有就继续分割，如果没有那么就在那边标记一下
        # 左上角
        if (dr < tr + s and dc < tc + s):
            self.ChessBord(tr, tc, dr, dc, s, BORD)
        else:
            BORD[tr + s - 1][tc + s - 1] = T
            self.AddRouter(T, (tr + s - 1, tc + s - 1))
            self.ChessBord(tr, tc, tr + s - 1, tc + s - 1, s, BORD)

        # 右上角
        if (dr < tr + s and dc >= tc + s):
            self.ChessBord(tr, tc + s, dr, dc, s, BORD)
        else:
            BORD[tr + s - 1][tc + s] = T
            self.AddRouter(T, (tr + s - 1, tc + s))
            self.ChessBord(tr, tc + s, tr + s, tc + s - 1, s, BORD)

        # 左下角
        if (dr >= tr + s and dc < tc + s):
            self.ChessBord(tr + s, tc, dr, dc, s, BORD)
        else:
            BORD[tr + s][tc + s - 1] = T
            self.AddRouter(T, (tr + s, tc + s - 1))
            self.ChessBord(tr + s, tc, tr + s, tc + s - 1, s, BORD)

        # 右下角
        if (dr >= tr + s and dc >= tc + s):
            self.ChessBord(tr + s, tc + s, dr, dc, s, BORD)
        else:
            BORD[tr + s][tc + s] = T
            self.AddRouter(T, (tr + s, tc + s))
            self.ChessBord(tr + s, tc + s, tr + s, tc + s, s, BORD)

    def GetRouters(self,SIZE,dr,dc,show=False)->dict:
        BORD = [[0 for x in range(SIZE)] for i in range(SIZE)]  # 初始化棋盘
        self.ChessBord(0,0,dr,dc,SIZE,BORD)
        if(show):
            self.showBordinConsole(BORD)
        return self.ROUTERS


if __name__ == '__main__':
    algorithm= Algorithm()
    routers = algorithm.GetRouters(4,1,3,show=True)
    for i in routers.keys():
        print(routers.get(i),"-----",i)

棋盘覆盖问题与可视化代码演示

整合UI

接下来就是整合我们的UI就好了，这里我们再搞一个控制代码


from Bord.BordPlace import Algorithm
from Bord.ShowDynamic import Board
import turtle
class ShowPlaceUI:
    def __init__(self,size,dr,dc):
        self.size = size
        self.dr = dr-1
        self.dc = dc-1
        self.algorithm = Algorithm()
        self.board = Board(self.size,self.dr,self.dc)
        self.colors = ["aqua","lime","yellow"]
    def run(self):

        routers = self.algorithm.GetRouters(self.size,self.dr,self.dc)
        # self.board.speed(10)
        for key in routers:
            points = routers.get(key)
            for point in points:
                color = self.colors[(key-1)%3]
                row,coloumn = point
                self.board.speed(100)
                self.board.drawfill(color,row,coloumn)

if __name__ == '__main__':

    showUi =  ShowPlaceUI(8,2,4)

    showUi.run()

    turtle.mainloop()

效果演示

棋盘覆盖问题与可视化代码演示