前情提要

在上篇文章当中详细介绍了棋盘覆盖问题的三种解法以及c++代码实现，不太清晰的同学可以看看思路棋盘覆盖问题详解.在文章最后提到了该问题的可视化工具，借助这篇文章和大家分享一下小工具的实现过程。

本工具借助pygame开发，不了解的同学可以自学了解一下。

import pygame
import time
import queue
#初始化pygame
pygame.init()
#获取对显示系统的访问，并创建一个窗口screen
#窗口大小为670x670
space = 60 # 四周留下的边距
cell_size =150 # 每个格子大小
cell_num = 5
grid_size = cell_size * (cell_num - 1) + space * 2 # 棋盘的大小
screencaption = pygame.display.set_caption('棋盘覆盖')
screen = pygame.display.set_mode((grid_size,grid_size+200)) #设置窗口长宽
g=[]
color=[(220,20,60),(0,0,255),(60,179,113),(255,255,0),(255,165,0)] #颜色：红，蓝，绿，浅黄，黄
i=0
title1=0 #分治时的骨牌编号
title2=0 #队列时的骨牌编号
title3=0 #栈时的骨牌编号
def show_dfs(tr,tc,dr,dc,size):
    #分治法
    if size==1:
        return
    global title1
    t=title1
    title1+=1
    s=size//2
    #print(f"tr={tr},tc={tc},dr={dr},dc={dc},size={s},t={t}")
    #左上
    if(dr<tr+s and dc<tc+s):
        show_dfs(tr,tc,dr,dc,s)
    else:
        #print(tr+s-1,tc+s-1)
        time.sleep(1)
        pygame.draw.rect(screen, color[t%5], [(tc+s-1) * cell_size + space, (tr + s - 1) * cell_size + space, cell_size, cell_size], 0)
        #print(f"左上：tr={tr},tc={tc},dr={dr},dc={dc},size={s},t={t}")
        pygame.display.update()
        show_dfs(tr,tc,tr+s-1,tc+s-1,s)
    #右上
    if(dr<tr+s and dc>=tc+s):
        show_dfs(tr,tc+s,dr,dc,s)
    else:
        time.sleep(1)
        pygame.draw.rect(screen, color[t%5],[(tc + s) * cell_size + space, (tr + s-1) * cell_size + space, cell_size, cell_size], 0)
        #print(f"右上：tr={tr},tc={tc},dr={dr},dc={dc},size={s},t={t}")
        pygame.display.update()
        show_dfs(tr,tc+s,tr+s-1,tc+s,s)
    #右下
    if(dr>=tr+s and dc>=tc+s):
        show_dfs(tr+s,tc+s,dr,dc,s)
    else:
        time.sleep(1)
        pygame.draw.rect(screen, color[t%5],[(tc + s) * cell_size + space, (tr + s) * cell_size + space, cell_size, cell_size], 0)
        #print(f"右下：tr={tr},tc={tc},dr={dr},dc={dc},size={s},t={t}")
        pygame.display.update()
        show_dfs(tr+s,tc+s,tr+s,tc+s,s)
    #左下
    if(dr>=tr+s and dc<tc+s):
        show_dfs(tr+s,tc,dr,dc,s)
    else:
        time.sleep(1)
        pygame.draw.rect(screen, color[t%5],[(tc + s-1) * cell_size + space, (tr + s) * cell_size + space, cell_size, cell_size], 0)
        #print(f"左下：tr={tr},tc={tc},dr={dr},dc={dc},size={s},t={t}")
        pygame.display.update()
        show_dfs(tr+s,tc,tr+s,tc+s-1,s)
def show_queue():
    #队列
    q=queue.Queue()
    data=[0,0,0,0,4]
    q.put(data)
    global title2
    while q.empty()==False:
        c=q.get()
        if(c[4]!=1):
            s=c[4]//2
            t=title2
            title2+=1
            tr=c[0]
            tc=c[1]
            dr=c[2]
            dc=c[3]
            if(dr<tr+s and dc<tc+s):
                q.put([tr,tc,dr,dc,s])
            else:
                time.sleep(1)
                pygame.draw.rect(screen, color[t%5],[(tc + s - 1) * cell_size + space, (tr + s - 1) * cell_size + space, cell_size, cell_size],0)
                pygame.display.update()
                q.put([tr,tc,tr+s-1,tc+s-1,s])

            if(dr<tr+s and dc>=tc+s):
                q.put([tr,tc+s,dr,dc,s])
            else:
                time.sleep(1)
                pygame.draw.rect(screen, color[t%5],[(tc + s) * cell_size + space, (tr + s-1) * cell_size + space, cell_size, cell_size], 0)
                pygame.display.update()
                q.put([tr,tc+s,tr+s-1,tc+s,s])

            if(dr>=tr+s and dc>=tc+s):
                q.put([tr+s,tc+s,dr,dc,s])
            else:
                time.sleep(1)
                pygame.draw.rect(screen, color[t%5],[(tc + s) * cell_size + space, (tr + s) * cell_size + space, cell_size, cell_size], 0)
                pygame.display.update()
                q.put([tr+s,tc+s,tr+s,tc+s,s])

            if(dr>=tr+s and dc<tc+s):
                q.put([tr+s,tc,dr,dc,s])
            else:
                time.sleep(1)
                pygame.draw.rect(screen, color[t%5],[(tc + s - 1) * cell_size + space, (tr + s) * cell_size + space, cell_size, cell_size], 0)
                pygame.display.update()
                q.put([tr+s,tc,tr+s,tc+s-1,s])
            q.put(c)
        else:
            break

def show_stack():
    #栈
    st=[]
    global title3
    st.append([0,0,0,0,4])
    while len(st)!=0:
        if (st[-1][4] != 1):
            s = st[-1][4] // 2
            t = title3
            title3 += 1
            tr = st[-1][0]
            tc = st[-1][1]
            dr = st[-1][2]
            dc = st[-1][3]
            st.pop()
            if (dr < tr + s and dc < tc + s):
                st.append([tr, tc, dr, dc, s])
            else:
                time.sleep(1)
                pygame.draw.rect(screen, color[t % 5],[(tc + s - 1) * cell_size + space, (tr + s - 1) * cell_size + space, cell_size,cell_size], 0)
                pygame.display.update()
                st.append([tr, tc, tr + s - 1, tc + s - 1, s])

            if (dr < tr + s and dc >= tc + s):
                st.append([tr, tc + s, dr, dc, s])
            else:
                time.sleep(1)
                pygame.draw.rect(screen, color[t % 5],[(tc + s) * cell_size + space, (tr + s - 1) * cell_size + space, cell_size, cell_size],0)
                pygame.display.update()
                st.append([tr, tc + s, tr + s - 1, tc + s, s])

            if (dr >= tr + s and dc >= tc + s):
                st.append([tr + s, tc + s, dr, dc, s])
            else:
                time.sleep(1)
                pygame.draw.rect(screen, color[t % 5],[(tc + s) * cell_size + space, (tr + s) * cell_size + space, cell_size, cell_size], 0)
                pygame.display.update()
                st.append([tr + s, tc + s, tr + s, tc + s, s])

            if (dr >= tr + s and dc < tc + s):
                st.append([tr + s, tc, dr, dc, s])
            else:
                time.sleep(1)
                pygame.draw.rect(screen, color[t % 5],[(tc + s - 1) * cell_size + space, (tr + s) * cell_size + space, cell_size, cell_size],0)
                pygame.display.update()
                st.append([tr + s, tc, tr + s, tc + s - 1, s])
        else:
            st.pop()

def clear():
    draw_map()

def move(pos):
    #监听鼠标
    x1=pos[0]
    y1=pos[1]
    x = round((pos[0] - space) / cell_size)
    y = round((pos[1] - space) / cell_size)
    global cnt,i
    if(x>=0 and y>=0 and x<=3 and y<=3):
        pygame.draw.rect(screen, color[i%5], [x * cell_size + space, y * cell_size + space,cell_size,cell_size],0)
    if(x1>=bx1 and x1<=bx1+bw1 and y1>=by1 and y1<=by1+bh1):
        i=0
    if (x1 >= bx2 and x1 <= bx2 + bw2 and y1 >= by2 and y1 <= by2 + bh2):
        i = 1
    if (x1 >= bx3 and x1 <= bx3 + bw3 and y1 >= by3 and y1 <= by3+bh3):
        i = 2
    if (x1 >= bx4 and x1 <= bx4 + bw4 and y1 >= by4 and y1 <= by4+bh4):
        i = 3
    if (x1 >= bx5 and x1 <= bx5 + bw5 and y1 >= by5 and y1 <= by5 + bh5):
        i = 4
    if(x1>=bx6 and x1<=bx6+bw6 and y1>=by6 and y1<=by6+bh6):
        show_dfs(0,0,0,0,4)
    if (x1 >= bx7 and x1 <= bx7 + bw7 and y1 >= by7 and y1 <= by7 + bh7):
        show_queue()
    if (x1 >= bx8 and x1 <= bx8 + bw8 and y1 >= by8 and y1 <= by8 + bh8):
        show_stack()
    if(x1>=bx10 and x1<=bx10+bw10 and y1>=by10 and y1<=by10+bh10):
        clear()
def draw_map():
    screen.fill((255,255,255))

    global bx1, bx2, bx3, by1, by2, by3, bw1, bw2, bw3, bh1, bh2, bh3, bx4, by4, bw4, bh4, bx5, by5, bw5, bh5, bx6, by6, bw6, bh6, bx7, by7, bw7, bh7, bx8, by8, bw8, bh8, bx9, by9, bw9, bh9
    global bx10,by10,bw10,bh10

    bx1 = space
    by1 = grid_size
    bw1 = 80
    bh1 = 30

    bx2 = space
    by2 = grid_size + 50
    bw2 = 80
    bh2 = 30

    bx3 = space
    by3 = grid_size + 100
    bw3 = 80
    bh3 = 30

    bx4 = cell_size + space
    by4 = grid_size
    bw4 = 80
    bh4 = 30

    bx5 = cell_size + space
    by5 = grid_size + 50
    bw5 = 80
    bh5 = 30

    bx6=3 * cell_size + space
    by6=grid_size
    bw6=70
    bh6=50

    bx7 = 3 * cell_size + space
    by7 = grid_size+70
    bw7 = 70
    bh7 = 50

    bx8 = 3 * cell_size + space
    by8 = grid_size+140
    bw8 = 70
    bh8 = 50

    bx10=3 * cell_size + space+90
    by10 = grid_size + 140
    bw10=70
    bh10=50

    for x in range(0, cell_size * cell_num, cell_size):
        pygame.draw.line(screen, (0, 0, 0), (x + space, 0 + space),
                         (x + space, cell_size * (cell_num - 1) + space), 1)
    for y in range(0, cell_size * cell_num, cell_size):
        pygame.draw.line(screen, (0, 0, 0), (0 + space, y + space),
                         (cell_size * (cell_num - 1) + space, y + space), 1)
    pygame.draw.rect(screen, (0,0,0), [0 * cell_size + space, 0 * cell_size + space, cell_size, cell_size], 0)

    #颜色按钮
    pygame.draw.rect(screen,(220,20,60), [0 * cell_size + space, grid_size, 80, 30], 0)
    pygame.draw.rect(screen, (0,0,255), [0 * cell_size + space, grid_size+50, 80, 30], 0)
    pygame.draw.rect(screen, (60,179,113), [0 * cell_size + space, grid_size + 100, 80, 30], 0)
    pygame.draw.rect(screen, (255,255,0), [1 * cell_size + space, grid_size, 80, 30], 0)
    pygame.draw.rect(screen, (255,165,0), [1 * cell_size + space, grid_size+50, 80, 30], 0)

    #功能按钮
    pygame.draw.rect(screen,(211,211,211),[3 * cell_size + space, grid_size, 70, 50],0)
    pygame.draw.rect(screen, (211, 211, 211), [3 * cell_size + space, grid_size+70, 70, 50], 0)
    pygame.draw.rect(screen, (211, 211, 211), [3 * cell_size + space, grid_size+140, 70, 50], 0)
    pygame.draw.rect(screen, (211, 211, 211), [3 * cell_size + space+90, grid_size + 140, 70, 50], 0)

    # 添加文字
    font = pygame.font.Font('FZZJ-QNTJW.TTF', 30)
    text1 = font.render('分治', True, (0, 0, 0))
    text2 = font.render('队列', True, (0, 0, 0))
    text3 = font.render('栈', True, (0, 0, 0))
    text4=font.render('清空', True, (0,0,0))
    tw1, th1 = text1.get_size()
    tw2, th2 = text2.get_size()
    tw3, th3 = text3.get_size()
    tw4,th4=text4.get_size()
    tx1 = bx6 + bw6 / 2 - tw1 / 2
    ty1 = by6 + bh6 / 2 - th1 / 2
    tx2 = bx7 + bw7 / 2 - tw2 / 2
    ty2 = by7 + bh7 / 2 - th2 / 2
    tx3 = bx8 + bw8 / 2 - tw3 / 2
    ty3 = by8 + bh8 / 2 - th3 / 2
    tx4 = bx10 + bw10 / 2 - tw4 / 2
    ty4 = by10 + bh10 / 2 - th4 / 2

    screen.blit(text1, (tx1, ty1))
    screen.blit(text2, (tx2, ty2))
    screen.blit(text3, (tx3, ty3))
    screen.blit(text4, (tx4, ty4))
    pygame.display.update()


    pygame.display.flip()
def run():
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                exit()
            # pygame.display.flip()  # 对每次操作进行界面刷新
            if event.type == pygame.MOUSEBUTTONDOWN:
                #响应鼠标
                move(event.pos)
                time.sleep(1)
            pygame.display.update()
if __name__=='__main__':
    draw_map()
    run()