preface
Unconsciously, this blog is my 200th blog published in CSDN, and it is also the 100th + blog in digging gold. The future can be expected, volume! Roll!!!! Roll!!!!
The board cover
Today we are going to make a checkerboard covering thing, this is also a small question left by a teacher, so let the little ye to end
describe
It’s very simple, it’s a checkerboard, and then the checkerboard is 2 to the k by 2 to the k, and then there’s an obstacle, and now you have to cover the checkerboard with four dominoes without covering the obstacle. The diagram below:
So the problem is this problem, and the idea is the typical divide-and-conquer. And of course that’s that’s also the question, what’s the divide-and-conquer, what’s the strategy. Let’s take a look at what we ended up doing
Train of thought
When we say divide and conquer, we’re going to have to use recursion, and when we say recursion we’re going to have to talk about at least two cases, the beginning and the end states. Knowing the start state is good for writing the process, and knowing the end state is good for writing the end state.
start
Having said that, divide and conquer, then it has to be a problem of partition, of subproblem, and for a 2 by 2 checkerboard, we just have to think about where the hindrance points are, and then we cover up the points of move so that’s what we want, like this.
So all we have to think about with a big chessboard is dividing, dividing a big chessboard over and over, building the same subproblems every time we divide.
Subproblem construction
So, what is a subproblem? A subproblem is a region that looks like the picture above, and then you solve the problem in that region. So how do we do it? This way.
The end of the
At this point we see the smallest problem (the smallest problem), when 2×2, we follow our intermediate process, we will cover everything around, and then partition, at that point it will become 1×1 cells, obviously there is no need to continue to partition, exit.
Preliminary code
This time it is written in Python. Because it’s all about graphics, right, and using the new syntax features python introduced a year ago for fun. This is now our console output program. But be careful here to preserve the way we overwrite it.
TIMES = 1 # Number of placements
ROUTERS = dict(a)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
# keep splitting until size is 1
if(size == 1) :return
T = TIMES # The current overlay
TIMES +=1
s = int(size/2) # Start doing splits
# Start from four directions to determine whether there is a square, if not continue to divide, if not so mark there
# the upper left corner
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)
# the top right corner
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)
# the bottom left corner
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)
# the bottom right hand corner
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)] Initialize the board
ChessBord(0.0,dr,dc,SIZE,BORD)
showBord(BORD)
for i in ROUTERS.keys():
print(ROUTERS.get(i))
Copy the code
Graphical Upgrade
The next step is to upgrade the graphics. This is easy. I’m just going to use the turtle drawing
Drawing board
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() # draw checkerboard
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) # Switch directions
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) :
Is responsible for converting the coordinates above that matrix to the coordinates in the UI interface
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)
# Color the grid
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) :
# recovery
if(self.isdown()):
self.penup()
self.home()
self.goto(self.startx, self.starty) # starting point
if __name__ == '__main__':
board = Board(8.2.2)
turtle.mainloop()
Copy the codeThere’s a pit, and that’s the goto(), and that’s the center coordinate, and I just adjusted it for about half a day, and it’s killing me.
integration
Now we can start integrating our code.
Integration algorithm
class Algorithm:
def __init__(self) :
self.TIMES = 1
self.ROUTERS = dict(a)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) :
# keep splitting until size is 1
if (size == 1) :return
T = self.TIMES # The current overlay
self.TIMES += 1
s = int(size / 2) # Start doing splits
# Start from four directions to determine whether there is a square, if not continue to divide, if not so mark there
# the upper left corner
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)
# the top right corner
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)
# the bottom left corner
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)
# the bottom right hand corner
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)] Initialize the board
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)
Copy the code
Integration of the UI
The next step is to integrate our UI, and here we have another control code
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()
Copy the code