您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q59: 合并单元格的方式

时间:12-31来源:作者:点击数:

1. 问题描述

2. 解题分析

似曾相似燕归来。。。

第一感就认出了这道题目跟之前“Q32:榻榻米的铺法”的相似之处,本题完全可以看作是Q32的增强版。在Q32中,榻榻米的尺寸是固定的1x2的大小。而本题可以看作是用任意尺寸长方形或正方形对房间铺设的问题!

基于这一认识,可以直接基于Q32的题解进行一些适当修改就可以的得到本题的题解。喜欢挑战的小伙伴如果没有做过前面的Q32(或者做过了但是记忆模糊了)的话,可以先独立做做这道题目,如果卡住了再回头去看一下Q32的题解看看能不能得到启发。最后还是卡住了的话,再看以下题解。

基于Q32的题解方案,有以下要点:

  1. 外加围栏,以方便判断
  2. 行扫描(或者列扫描也可以,道理相同),以很小的冗余扫描代价来换取巨大的判断简化的利益
  3. 从某一个点出发的可能的合并(对应于榻榻米铺法)方法的遍历。

第3点这是本题与Q32的本质的差异点。这里就不解释了,直接看代码很简单明了。单就代码而言甚至比Q32的还要简单。

其中利用到了numpy.any()函数用于判断某矩形区域内是否全0。因为本题中并没有要求给出合并方案的图示化(事实上也不可能,因为种类数之多远远超出了直感),所以在递归调用时没有给合并块(“榻榻米”)编号并标记到格点内,而只是简单地用“0”表示空格,“1”表示已经被合并的格子。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Sat Oct 16 08:23:03 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque
import itertools as it
import numpy as np

H = 4 # Height, vertical
W = 4 # Width,  horizontal

# cells initialization, with a guard band surrounding the original cells
# The guard band is initialized to '-1' to simplify the judgement processing.
cells = np.zeros((H+2, W+2))
cells[0,:] = -1
cells[H+1,:] = -1
cells[:,0] = -1
cells[:,W+1] = -1

count = 0

def combine_cells(h,w)->int:
    '''
    Parameters
    ----------
    (h,w) : The current exploration point. 
            h represents row index, w represents col index.
    Returns: int
        The number of total arrangement starting from the point (h,w), together 
        with the current cells status, which is a global variable

    '''        
    global count
    
    # print(h,w,idx)
    if   h == H + 1:
        count = count + 1
        # print(cells)    
    elif w == W + 1: 
        # Reach the right boundary, go to explore the next row from the left 
        combine_cells(h+1, 1)
    elif cells[h,w] > 0: 
        # This grid has been occupied, move to the right one
        combine_cells(h, w+1)
    else:
        for i in range(h,H+1):
            for j in range(w,W+1):
                # Judge whether (h,w)--(i,j) ractangulat can be combined.
                # Here, (h,w) represents top-left corner, (i,j) represent right-down corner
                if ~np.any(cells[h:i+1,w:j+1]):
                    cells[h:i+1,w:j+1] = 1
                    combine_cells(h, j+1)
                    cells[h:i+1,w:j+1] = 0
                            
tStart = time.perf_counter()
combine_cells(1, 1)
tCost  = time.perf_counter() - tStart
print('count = {0}, tCost = {1:6.3f}(sec)'.format(count,tCost))  

运行结果:count = 70878, tCost = 1.471(sec)

4. 后记

原书中给出了好几页的分析和题解。没有耐心看(反正已经有了个解垫底^-^),而且可能也很难看懂。这种问题思路上没有对上路的话,尽量别人blabla说一大堆估计也很难跟得上。相信很多小伙伴们都会有同感。

尽管这道题目在本书中是属于高级篇,但是基于Q32我几乎瞬间就得出的解决方案。由此也说明循序渐进的积累的重要性。

这个结果非常反直觉,小小的4*4的网格区间的单元合并居然能够整出这么多种的可能性,真的是很神奇。

另外,本题还有个进一步的要求是,求最后不包含1x1尺寸格子(也就是不允许有未合并的单元格)的合并方案数。这个只需要在以上题解中稍作条件修改就可以得到。留给有兴趣的小伙伴们自己尝试,答案是1208种。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门