二维数组对角遍历的BFS解决方案

Question

我正在努力解决这个问题Diagonal Traverse - LeetCode

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Output:  [1,2,4,7,5,3,6,8,9]

Explanation:

Note:

The total number of elements of the given matrix will not exceed 10,000.

这个问题可以被视为bfs从根（0，0）遍历到目标（行，列）

在阅读了所有提交的材料和讨论之后，我找到了一个相对简洁的解决方案

class Solution:
    def findDiagonalOrder(self, matrix: 'List[List[int]]') -> 'List[int]':
        if len(matrix) == 0:
            return []
        r, c = 0, 0
        rows, cols = len(matrix), len(matrix[0])
        res = []
        for _ in range(rows * cols):
            res.append(matrix[r][c])
            if (r + c) % 2 == 0:
                if c == cols - 1: #column boundary 
                    r += 1
                elif r == 0: # 
                    c += 1
                else: #move up 
                    r -= 1
                    c += 1
            else:
                if r == rows - 1: #row boundary 
                    c += 1
                elif c == 0:
                    r += 1
                else:#move down 
                    r += 1
                    c -= 1
        return res

我有一种感觉，这样的解决方案是不够好的，因为太多的劳力使用多个条件检查。你知道吗

对于这类问题可能有一个通用的解决方案，可以在以后用最小的努力来解决对角线遍历问题。你知道吗

问题是从（0，0）移动到（4，4）

人物：
1对角线上每个节点的和等于步数
2可能有一个关系公式来从根（0,0）和上一级生成下一级中的所有节点。你知道吗

我的解决方案：

import unittest
import logging

logging.basicConfig(level=logging.DEBUG, format="%(levelname)s %(message)s")

class Solution:
    def findDiagonalOrder(self, matrix: 'List[List[int]]') -> 'List[int]':
        from collections import deque 
        #root is (0, 0)
        #destination is (rows, cols)
        r, c = 0, 0
        root = (r, c)
        rows, cols = len(matrix), len(matrix[0])  
        step = 0
        queue = deque([root]) 
        res = []

        while queue and r < rows and c < cols:
            step += 1
            size = len(queue)

            for _ in range(size):
                r, c = queue.popleft()
                res.append(matrix[r][c])

            #collect the next nodes 
            if r == 0 and c == 0: 
                c = step #(0, 1) determin the direction of the first step 
                queue.append((r,c))
                logging.debug(f"queue: {queue}")
                logging.debug(f"step: {step}, r:{r}, c: {c}")

            if c == 0:
                level = [(step-i, i) for i in range(step)]
            elif r == 0:
                level = [(i, step-i) for i in range(step)]
            queue += level 
            logging.debug(f"queue: {queue}")
            #raise Exception

        return res 

class MyCase(unittest.TestCase):
    def setUp(self):
        self.solution = Solution()

    def test_a(self):
        matrix = [
                    [ 1, 2, 3 ],
                    [ 4, 5, 6 ],
                    [ 7, 8, 9 ]
                ]
        answer = [1,2,4,7,5,3,6,8,9]
        check = self.solution.findDiagonalOrder(matrix)
        self.assertEqual(answer, check)

unittest.main()

然而，它停在

DEBUG queue: deque([(0, 2), (1, 1)])
DEBUG queue: deque([(0, 2), (1, 1)])
DEBUG queue: deque([(0, 2), (1, 1)])
DEBUG queue: deque([(0, 2), (1, 1)])
^CDEBUG queue: deque([(0, 2), (1, 1)])
Traceback (most recent call last):

我没有写出一个好的关系公式来生成下一级的节点。你知道吗

你能给我一些提示吗？你知道吗

Answer 1

我不确定这是否能回答你的问题，但我可以与你分享我的方法，如果它足够简洁明了的话。你知道吗

<>代码是C++的，但是你可以理解这个想法。你知道吗

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> result;

        int n = matrix.size();
        if(n == 0) return result;
        int m = matrix[0].size();
        if(m == 0) return result;

        result.resize(m * n);
        int row = 0, col = 0, d = 0;
        int dir[2][2] = {
               {-1, 1},
               {1, -1}
        };

        for (int i = 0; i < m * n; i++) {
            result[i] = matrix[row][col];
            row += dir[d][0];
            col += dir[d][1];

            if (row >= n) { row = n - 1; col += 2; d = 1 - d; }
            if (col >= m) { col = m - 1; row += 2; d = 1 - d; }

            if (row < 0)  { row = 0; d = 1 - d;}
            if (col < 0)  { col = 0; d = 1 - d;}
        }
        return result;
    }
};

Answer 2

遍历方阵的解

class Solution:
    def findDiagonalOrder(self, matrix: 'List[List[int]]') -> 'List[int]':
        from collections import deque 

        if(len(matrix) == 0 or len(matrix[0]) == 0):
            return []

        if(len(matrix) == 1):
            return matrix[0]

        res = []
        if(len(matrix[0]) == 1):
            for row in matrix:
                res+=row
            return res  

        r, c = 0, 0
        root = (r, c)
        rows, cols = len(matrix), len(matrix[0])  
        step = 0
        queue = deque([root]) 
        left = []
        #forwards 
        while queue and step < rows:
            step += 1
            size = len(queue)

            for _ in range(size):
                r, c = queue.popleft()
                left.append(matrix[r][c])

            if r == 0:
                level = [(i, step -i) for i in range(step+1)] #(r, c+1)
            elif c == 0:
                level = [(step-i, i) for i in range(step+1)]             
            queue += level 
            #logging.debug(f"queue: {queue}")
            #logging.debug(f"left: {left}")
            #raise Exception

        #backwords 
        step = 0
        queue = deque([root]) 
        right  = []
        #forwards 
        while queue and step < rows-1:
            step += 1
            size = len(queue)

            for _ in range(size):
                r, c = queue.popleft()
                right.append(matrix[rows-r-1][cols-c-1])

            if r == 0:
                level = [(i, step -i) for i in range(step+1)] #(r, c+1)
            elif c == 0:
                level = [(step-i, i) for i in range(step+1)]             
            queue += level 
            #logging.debug(f"queue: {queue}")
            #logging.debug(f"right: {right}")
            #raise Exception
        right.reverse()
        res = left + right 
        return res