与前面的Q32、Q59以及后面的Q68(碰巧先做了Q68)是类似的搜索问题。有兴趣的小伙伴如果在思考本问题时卡住了可以先看看本系列的以上三题的题解看看是否能找到头绪,如果还是卡住了的话再看本题的题解吧^-^。
本题的基本搜索框架直接基于Q68(因为Q68是前几天刚做的记忆犹新改起来方便),
算法流程如下(代码中实际上用grids替代seats):
要点说明:
与Q68不同的地方在于:
本题最后还要进行白色格子形成的区域的连通性,这个是最大的不同点。处理方式参见下一节
本题要求填完色后,黑色格子不能分裂整个表格,这是这道题目与Q32,A59,Q68最大的差异之所在。换言之,白色格子构成的区域必须保持连通,这在图论算法中等价于reachability问题,即从某个白色格子出发只允许横向或纵向走一格的话能够到达任何其它的白色格子。解决Reachability问题的经典策略是深度优先搜索。
算法流程如下:
补充说明:
# -*- coding: utf-8 -*-
"""
Created on Wed Oct 20 07:28:54 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
H = 5 # Height, vertical
W = 6 # Width, horizontal
# grids initialization, with a guard band surrounding the original grids
# The guard band is initialized to '-1' to simplify the judgement processing.
grids = np.zeros((H+2, W+2))
grids[0,:] = -1
grids[H+1,:] = -1
grids[:,0] = -1
grids[:,W+1] = -1
count = 0
def isNG(h,w):
'''
'2' represents black.
Judge whether there are two neighbouring cells are all black
'''
return (grids[h,w]==2) and ((grids[h-1,w]==2) or (grids[h,w-1]==2))
def isAllWhiteConnected(grids)->bool:
# Find the first white grid, which is flaged as '1'
found = False
for i in range(H):
for j in range(W):
if grids[i+1,j+1] == 1:
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]] = 0 # Flag it to indicate that it has already been visited.
if curGrids[cur[0]-1,cur[1]] == 1: # Up grid
s.append((cur[0]-1,cur[1]))
if curGrids[cur[0]+1,cur[1]] == 1: # Down grid
s.append((cur[0]+1,cur[1]))
if curGrids[cur[0],cur[1]-1] == 1: # Left grid
s.append((cur[0],cur[1]-1))
if curGrids[cur[0],cur[1]+1] == 1: # Right grid
s.append((cur[0],cur[1]+1))
return not np.any(curGrids==1)
def arrange_grid(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 grids status, which is a global variable
'''
global count
# print('h = {0}, w = {1}'.format(h,w))
if h == H + 1:
if isAllWhiteConnected(grids):
count = count + 1
# print(grids)
elif w == W + 1: # Go to the next row.
# Reach the right boundary, go to explore the next row from the left
arrange_grid(h+1, 1)
# elif grids[h,w] > 0:
# # This grid has been occupied, move to the right one
# arrange_grid(h, w+1)
else:
# Try to arrange white to the current grid(h,w). This is always possible
grids[h,w] = 1
arrange_grid(h,w+1)
grids[h,w] = 0
# Try to arrange black to the current grid(h,w)
grids[h,w] = 2
if not isNG(h,w):
arrange_grid(h,w+1)
grids[h,w] = 0
# # Test of isAllWhiteConnected()
# grids[2,3] = 1
# grids[1,3] = 1
# # print(grids)
# print(isAllWhiteConnected(grids))
tStart = time.perf_counter()
arrange_grid(1, 1)
tCost = time.perf_counter() - tStart
print('(H,W)=({0},{1}), count = {2}, tCost = {3:6.3f}(sec)'.format(H,W,count,tCost))
运行结果:
(H,W)=(3,4), count = 121, tCost = 0.007(sec)
(H,W)=(4,5), count = 2749, tCost = 0.244(sec)
(H,W)=(5,6), count = 149283, tCost = 20.695(sec)
速度上应该还有优化空间,且等我扫描完所有题目再回头来做第二轮清理工作。。。
高级篇竟然是倒着做过来(Q69-->Q68-->Q67-->Q66...)的,不是有意为之。我一般先读一遍题目(不看原书提示和解答),如果5到10分钟内还没有什么头绪,就转向下一道题,碰到似曾相似或者有头绪觉得有可能搞定的先动手,然后就成了这样一个顺序。。。向前面Q56那种鬼脚图为题材的题目完全摸不着头脑,只能先在脑袋里存放一下