算法题(8)

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://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维数组。

请我喝瓶饮料