程序员的算法趣题Q61: 不交叉一笔画下去

1. 问题描述

根据题意要求：

1. 各节点不能重复访问。相应地，边也不会出现重复访问的情形
2. 由节点序列表示路径的话，正序列和逆序列表示相同的路径，不重复计算

2. 解题分析

深度优先路径遍历问题。从每一个节点出发，按照题设要求的规则进行深度优先搜索，每遍历完一次计数一次。

基本算法流程如下：

就是这么简单粗暴（简洁明了），这就是套路的力量^-^

要点说明：

1. Nodes为全1就表示找到了一条遍历路径（完成了一次无交叉一笔画）
2. 在每个节点处，探索上下左右是否可以画。不能出边界，外加的围栏节点初始化为“-1”，起到了保护和简化判断作用。
3. 由于要对nodes进行赋值以表示visited状态，所以在每次递归调用前要赋值，递归调用后要恢复。另外用visited来存储已访问信息会让问题变简单吗？对于此类（网格、棋盘等）问题似乎不会，甚至更麻烦。
4. 由于从任何一个节点出发都可以，因此外层需要对起始节点进行全扫描

以上流程没有考虑排除正序列和逆序列重复搜索的问题，因此浪费了一半的时间，所得答案要除以2才是正确答案。目前暂时没有想到如何排除正序列和逆序列重复搜索，暂时就此将就。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Thu Oct 21 07:32:03 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

# 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

count = 0

def dfs(h,w,nodes):
    # print('dfs({0},{1},{2})'.format(h,w,nodes))
    global count
    if np.all(nodes[1:H+1,1:W+1]):
        count = count + 1
        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()    
for h in range(1,H+1):
    for w in range(1,W+1):
        cur_nodes = nodes0.copy()
        cur_nodes[h,w] = 1
        dfs(h,w,cur_nodes)
        cur_nodes[h,w] = 0
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 = 124, tCost = 0.017(sec)

(H,W)=(4,5), count = 2012, tCost = 1.176(sec)

(H,W)=(5,6), count = 53992, tCost = 204.012(sec)

如上所述，将以上结果除以2才是正确答案。

4. 后记

以上只考虑了最基本解决方案，甚至连正逆序列重复搜索都没有排除，所以运行效率太低了。需要考虑优化，除了正逆序列重复搜索的排除外，还要进一步从缩小搜索范围或者剪枝（键盘敲出ｊｉｅｚｈｉ变换半天看着不对劲。。。最后回过神来是ｊｉａｎｚｈｉ非ｊｉｅｚｈｉ＾－＾）等角度考虑进一步提高搜索效率。

一般来说，但凡我能有一个哪怕最naive的解，我尽量避免看原书题解。要等我觉得关于这个问题已经想无可想的时候才去看原书题解。反正也不赶时间，只是利用闲暇时刻想一想（脑袋里可能并行地放了多个问题，没事的时候就翻出来想一想，所以也不浪费时间）。真正独立想出解决方案来才能有最大收获，这个也算是物尽其用吧，毕竟碰到一个好问题的机会难得。