目錄

1. 問題描述

2. 解題分析

3. 代碼及測驗

4. 后記

1. 問題描述

這道題的描述應該是有問題的（不知道是原文的問題還是翻譯的問題），

前面的描述中提到“前后左右的座位一定都是異性”和NG示例中的“前后左右全是同性”兩種情況，問題中所要求滿足的“上述條件”是什么呢？僅從背景關系來看第一感當然是說“前后左右的座位一定都是異性”，但是仔細一想就知道這個不對，每個座位的“前后左右的座位都是異性”的安排情況只有兩種，

“前后左右的座位一定都是異性”和“前后左右全是同性”的兩種極端情況之間還有巨大的灰色空間，問題的原意應該是指滿足“任何一個座位的前后左右都不全是同性”的情況吧？

2. 解題分析

先考慮一個基本方案，

從搜索方式來說，這個問題與前面的Q32和Q59等題有類似之處，只需要基于Q32或Q59的基本框架略作修改即可，

要點說明：

1. 與Q32, Q59一樣，逐行掃描，每次向右移一格，右邊到頭即移到下一格，到達最下邊的圍欄行則表明已經完成一次搜索，找到一個合規的安排方案
2. “違規檢查”只需要針對當前座位的左邊座位和上邊座位，這是因為掃描是向右、下方向進行的，當前座位的右邊和下邊還沒有安排人，所以右邊座位和下邊座位肯定還沒有違規
3. 最后還必須滿足男生和女生人數都必須相等

3. 代碼及測驗

# -*- coding: utf-8 -*-
"""
Created on Tue Oct 19 07:39:48 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

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

count = 0

def isNG(h,w):
    if seats[h,w] == -1:
        return False
    return (seats[h+1,w]==seats[h,w] or seats[h+1,w]==-1) and \
           (seats[h-1,w]==seats[h,w] or seats[h-1,w]==-1) and \
           (seats[h,w+1]==seats[h,w] or seats[h,w+1]==-1) and \
           (seats[h,w-1]==seats[h,w] or seats[h,w-1]==-1) 
    

def arrange_seat(h,w, boy, girl)->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 seats status, which is a global variable

    '''        
    global count
    # print('h = {0}, w = {1}'.format(h,w))
    if   h == H + 1:
        if boy == girl:
            count = count + 1
        # print(seats)    
    elif w == W + 1: # Go to the next row.
        # Reach the right boundary, go to explore the next row from the left 
        arrange_seat(h+1, 1, boy, girl)
    # elif seats[h,w] > 0: 
    #     # This grid has been occupied, move to the right one
    #     arrange_seat(h, w+1)
    else:
        # Try to arrange boy to the current seat(h,w)
        seats[h,w] = 1
        if not (isNG(h-1,w) or isNG(h,w-1) or isNG(h,w)):
            arrange_seat(h,w+1, boy+1, girl)            
        seats[h,w] = 0
        # Try to arrange girl to the current seat(h,w)
        seats[h,w] = 2
        if not (isNG(h-1,w) or isNG(h,w-1) or isNG(h,w)):
            arrange_seat(h,w+1, boy, girl+1)            
        seats[h,w] = 0
                                    
tStart = time.perf_counter()
arrange_seat(1, 1, 0, 0)
tCost  = time.perf_counter() - tStart
print('count = {0}, tCost = {1:6.3f}(sec)'.format(count,tCost))  

運行結果：

[3,4]: count = 354, tCost = 0.014(sec)

[4,5]: count = 34874, tCost = 1.649(sec)

[5,6]: count = 13374192, tCost = 803.130(sec)

4. 后記

跟昨天的Q69一樣，給出一個功能正確的方案并不難，但是運行太慢了！所以這些問題的難點在于如何提高運行效率，比如說書中所提示的剪枝，還有memoization等啊？容我再想一想，，，

上一篇：Q67: 不挨著坐是一種禮節嗎？

下一篇：Q69: 藍白歌會(1)

本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解