程序员的算法趣题Q60: 分割为同样大小

时间：01-01来源：作者：点击数：43

1. 问题描述

2. 解题分析

由于题目要求说“如果分割线已知，即使两个部分的颜色相反也看作是同一种分割方法”，这其实是说两种颜色是对称的，关键的是分割线的形状。“分割线这一侧涂成颜色1和另一侧涂成颜色2”与“分割线这一侧涂成颜色1和另一侧涂成颜色2”，是相同的。

2.1 思路1

最直观的方法是，随机挑选一半的格子涂成一种颜色，另一半涂成另一种颜色。然后判断两个颜色的区域各自的连通性。

4*5的区域有20个格子，所以分区的组合数有 $\binom{20}{10}=184756$ 种，针对其中每种都要做两次连通性检测，两个颜色各一次，因为一个颜色连通不能保证另一个颜色的连通。连通性检测在Q66中“已经”出现了（因为我恰好先做了Q66），在Q66中只需要做单方面的连通性检测。

2.2 思路2

把问题看作是划分割线的问题。从边上某点开始沿内部格子的边画不相交无重复的线直到到达另外一个边上的点为止，这样划好后自然地保证边的“两侧”的区域格子连通。然后判断这个边界“两侧”的格子数是否相等。

分割线示意图如下所示：

2.3 思路3

从区域生长的角度来考虑。

由于前面说了分割线形状相同，即便两个区域着色不同也算同一种情况。而左上角总是属于某一种颜色，所以可以考虑从左上角开始（当然考虑从任何一个格子开始都可以，都是等价的）。考虑从左上角开始始终以挨着（即保持连通性）的方式生长，每次增加一个格子着同样的颜色，直到生长区域的总面积等于一半。然后再检查未着色（或者说是着另一种颜色）的区域是否连通。

本题解采用思路3来实现。

问题可以看作是深度优先路径遍历问题。从每一个节点出发，按照题设要求的规则进行深度优先搜索，每遍历完一次计数一次。与Q61相类似（恰好先做了Q61^-^），所以算法流程基于Q61的流程进行修改。

但是要注意的是，以本思路这种区域生长方式，有可能按不同顺序生长出相同的着色方式，因此需要进行重复性检验。以下用visited来存储已经访问过的着色方式，以避免重复。

基本算法流程如下：

与Q61的另一个差异是在Q61中，从不同点出发是代表不同的情况，而本题中从任何点出发是等价的，因为关心的是最终划分好的分割线形状，因此本题固定从左上角格子出发，而不需要对出发点进行扫描。

2.4 连通性检查

同Q66的做法。

本题着色时是将格子填为1，未着色区域则保持为初始化的0。这样“1”区域生长结束后，只需要对“0”区域判断连通性（生长过程已经保证了“1”区域是连通的）。在图论算法中连通性问题等价于reachability问题，即从某个格子出发只允许横向或纵向走一格的话能够到达的所有格子。解决Reachability问题的经典策略是深度优先搜索。

算法流程如下：

补充说明：

本题中可以直接将已经访问的格子置为别的值，因此不需要另设visited来记录已访问的节点。这样做的好处是对于最后判断是否还有没有访问到的格子也很方便
最后判断是否还有为1的格子。有的话表示还有color格子未被访问到，即color区域不是连通的。

def isConnected(grids, color)->bool:    
    # Find the first color-grid, which is flaged as color.
    found = False
    for i in range(H):
        for j in range(W):
            if grids[i+1,j+1] == color:
                start = (i+1,j+1)
                found = True
                break
        if found:
            break
    # print(start)
        
    curGrids = grids.copy()            
    s = deque() # Used as stack, LIFO
    # visited = set() # No need of visited in this problem
    s.append(start)
    # visited.add(start)
    while len(s) > 0:
        cur = s.pop()
        # print(cur)
        curGrids[cur[0],cur[1]] = -1 # Flag it to indicate that it has already been visited.
        if curGrids[cur[0]-1,cur[1]] == color: # Up grid
            s.append((cur[0]-1,cur[1]))
        if curGrids[cur[0]+1,cur[1]] == color: # Down grid
            s.append((cur[0]+1,cur[1]))
        if curGrids[cur[0],cur[1]-1] == color: # Left grid
            s.append((cur[0],cur[1]-1))
        if curGrids[cur[0],cur[1]+1] == color: # Right grid
            s.append((cur[0],cur[1]+1))        
    return not np.any(curGrids==color)

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Fri Oct 22 07:31:06 2021

@author: chenxy
"""
import sys
import time
import datetime
import math
# import random
from   typing import List
from   collections import deque
import itertools as it
import numpy as np

print(__doc__)

def isConnected(grids, color)->bool:    
    #...


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

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

visited = set()

count = 0

def dfs(h,w,nodes):
    # print('dfs({0},{1},{2})'.format(h,w,nodes))
    global count
    if np.sum(nodes[1:H+1,1:W+1]) == (H*W)//2:
        # print(nodes[1:H+1,1:W+1])
        t = tuple(np.reshape(nodes[1:H+1,1:W+1], (H*W,)))
        if t not in visited:            
            # Judge whether all 0-grids are connected.
            if isConnected(nodes,0):
                count = count + 1
            visited.add(t)
        return
    
    if nodes[h-1,w] == 0:
        nodes[h-1,w] = 1
        dfs(h-1,w,nodes)
        nodes[h-1,w] = 0
    if nodes[h+1,w] == 0:
        nodes[h+1,w] = 1
        dfs(h+1,w,nodes)    
        nodes[h+1,w] = 0
    if nodes[h,w-1] == 0:
        nodes[h,w-1] = 1
        dfs(h,w-1,nodes)    
        nodes[h,w-1] = 0
    if nodes[h,w+1] == 0:
        nodes[h,w+1] = 1
        dfs(h,w+1,nodes)    
        nodes[h,w+1] = 0        
    
tStart = time.perf_counter()    
# STart from top-left grid
nodes0[1,1] = 1
dfs(1,1,nodes0)
tCost  = time.perf_counter() - tStart
print('(H,W)=({0},{1}), count = {2}, tCost = {3:6.3f}(sec)'.format(H,W,count,tCost))