Fork me on GitHub

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc

问题描述

蛇形遍历矩阵
按下图的方法蛇形遍历矩阵
矩阵为m行n列

此处输入图片的描述

解题思路

观察可以发现

结论1. 在矩阵中移动的动作

只有以下4种

此处输入图片的描述

4种动作,对应的向量分别为
1)(0,1)
2) (1, -1)
3) (1, 0)
4) (-1, 1)

结论2

对于动作1和动作3 最多连续走一步
对于动作2和动作4,保持动作到矩阵边界

结论3

如果要变换方向则按照上次动作的Next动作开始尝试
沿着动作1、动作2、动作3、动作4的顺序进行尝试

完整程序

# -*- coding: utf-8 -*-

actions = [(0,1), (1, -1), (1,0), (-1, 1)]
def snake(matrix, m, n):
    # start
    # (0, 0)
    # end 
    # (m - 1, n - 1)
    pos = (0, 0)
    num = 1
    matrix[pos[0]][pos[1]] = num
    last_action_idx = None
    while pos != (m-1, n-1):
        num += 1
        print "***************"
        print "current pos=", pos
        print "prepare to num", num, last_action_idx 
        print "last action", last_action_idx 
        print 
        # 尝试走出一步
        if last_action_idx is None:
            last_action_idx = 0
        # 尝试继续按原动作前进且下一个位置也是合法的
        # 继续走
        elif last_action_idx in set([1, 3]) and valid(matrix, pos, actions[last_action_idx], m, n):
            pass
        else: # 必须要换方向

            for i in xrange(4):
                last_action_idx = (last_action_idx + 1) % 4
                if valid(matrix, pos, actions[last_action_idx], m, n):
                    break

        print "execute action", last_action_idx
        action = actions[last_action_idx]
        pos = (pos[0] + action[0], pos[1] + action[1])
        print 'track', pos, num
        matrix[pos[0]][pos[1]] = num



def valid(matrix, pos, action, m, n):
    pos = (pos[0] + action[0], pos[1] + action[1])
    # 不能超过边界,且从来没有走过
    if pos[0] >= 0 and pos[0] < m and pos[1] >= 0 and\
            pos[1] < n and matrix[pos[0]][pos[1]] == 0:
        return True

    return False


def print_matrix(matrix):
    for line in matrix:
        for item in line:
            print item,
        print 
        print '-' * 10


if __name__ == '__main__':
    matrix = []
    matrix.append([0,0,0])
    matrix.append([0,0,0])
    matrix.append([0,0,0])
    matrix.append([0,0,0])

    snake(matrix, 4, 3)
    print "result", '=' * 10
    print_matrix(matrix)

总结

这类问题的核心是寻找规律,规律找到了,问题也就迎刃而解了。与之类似的还有螺旋遍历2维数组。


如果我的文章对你有帮助,你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。

微信支付码

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据