目錄
1. 問題描述
2. 解題分析
2.1 基本演算法流程
2.2 連通性檢查
3. 代碼及測驗
4. 后記
1. 問題描述
2. 解題分析
與前面的Q32、Q59以及后面的Q68（碰巧先做了Q68）是類似的搜索問題，有興趣的小伙伴如果在思考本問題時卡住了可以先看看本系列的以上三題的題解看看是否能找到頭緒，如果還是卡住了的話再看本題的題解吧^-^，
2.1 基本演算法流程
本題的基本搜索框架直接基于Q68（因為Q68是前幾天剛做的記憶猶新改起來方便），
演算法流程如下（代碼中實際上用grids替代seats）：
要點說明：
- 與Q32, Q59，Q68一樣，逐行掃描，每次向右移一格，右邊到頭即移到下一格，到達最下邊的圍欄行則表明已經完成一次搜索，找到一個合規的“預備”方案（因為還要做白色格子連通性檢查）
- “違規檢查”只需要針對當前填黑色的格子進行，這是因為掃描是向右、下方向進行，而且只需要檢查是否存在兩個相鄰格子都為黑色
與Q68不同的地方在于：
- 違規檢查不同
- 不要求黑、白格子數相同，因此search()函式不需要傳入各種顏色（對應Q68的boy/girl）的數量
本題最后還要進行白色格子形成的區域的連通性，這個是最大的不同點，處理方式參見下一節
2.2 連通性檢查
本題要求填完色后，黑色格子不能分裂整個表格，這是這道題目與Q32,A59,Q68最大的差異之所在，換言之，白色格子構成的區域必須保持連通，這在圖論演算法中等價于reachability問題，即從某個白色格子出發只允許橫向或縱向走一格的話能夠到達任何其它的白色格子，解決Reachability問題的經典策略是深度優先搜索，
演算法流程如下：
補充說明：
- 本題中可以直接將已經訪問的格子清零，因此不需要另設visited來記錄已訪問的節點，這樣做的好處是對于最后判斷是否還有沒有訪問到的格子也很方便
- 最后判斷是否還有為1的格子，有的話表示還有白色格子未被訪問到，即白色區域不是連通的，
3. 代碼及測驗
# -*- 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)
4. 后記
速度上應該還有優化空間，且等我掃描完所有題目再回頭來做第二輪清理作業，，，
高級篇竟然是倒著做過來（Q69-->Q68-->Q67-->Q66...）的，不是有意為之，我一般先讀一遍題目（不看原書提示和解答），如果5到10分鐘內還沒有什么頭緒，就轉向下一道題，碰到似曾相似或者有頭緒覺得有可能搞定的先動手，然后就成了這樣一個順序，，，向前面Q56那種鬼腳圖為題材的題目完全摸不著頭腦，只能先在腦袋里存放一下
上一篇：
下一篇：Q67: 不挨著坐是一種禮節嗎？
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/327904.html
標籤：其他
上一篇：程式員作息，現狀