整体放置。按格子编号由小到大的次序查找第一个可放置该组全部物品的空区域(空区域是指从某个空格子开始的同层连续的所有空格子) ,若找到,则在该空区域居中、连续放置该组全部物品,如下图所示。
零散放置。若所有空区域格子数都小于该组物品数,即找不到连续放置的空区域,则将该组每个物品按照从上到下,从左到右的顺序,依次放置到柜中的空格子中,具体次序如下图所示。
小明编写了一个Python程序实现上述功能,程序依次输入n、m代表柜子层数和柜子每层格子数,第三行输入物品组数k,接下来一行输入k个整数代表每组物品个数。程序运行后输出n*m的矩阵代表物品的放置情况,1表示当前格子放置物品,0表示当前格子没有放置物品,运行结果如下图所示。
编写函数init(),功能为预处理i层j列格子开始的同层连续的所有空格子数,保存在数组v中。v[i][j]=0表示i层j列格子不是空格子,v[i][j]=x代表i层j列格子开始的同层连续的所有空格子数为x,代码如下
def init(): for i in range(n): for j in range(m): if q[i][j]==0: k=j+1 while k<m and q[i][k] !=1: k+=1 ① else: v[i][j]=0 |
编写函数getpos(L),功能为寻找查找空格子数>=L的第一个空区域,若找到,返回该空区域的起始坐标[x,y],表示第x层,第y个格子开始的连续空格子的数量大于等于L,否则返回-1
def getpos(L): ret=-1 for i in range(n): for j in range(m): if ② : ret=[i,j] return ret return ret |
解决问题的主程序如下:
n=int(input()) #输入层数 m=int(input()) #输入列数 k=int(input()) #输入物品组数 q=[[0 for i in range(m)] for j in range(n)] # q 保存柜子的放置情况 v=[[0 for i in range(m)] for j in range(n)] # v 的含义参考 init 函数 init() #预处理 s=input() #输入每组物品数量 a=s.split() for i in range(k): a[i]=int(a[i]) start=0 for i in range(k): p=getpos(a[i]) if p!=-1: row=p[0] col=p[1] k= ③ k=k//2 t=col for j in range(k, 0, -1): v[row][t]=j #更新 v 数组 t=t+1 for j in range(t,t+a[i]): q[row][j]=1 v[row][j]=0 else: cnt=0 while : row=start//m col=start%m if q[row][col]==0: q[row][col]=1 v[row][col]=0 cnt+=1 start+=1 #输出放置情况 for i in range(n): for j in range(m): print(q[i][j], end=" ") print( ) |