Блог

Я хочу написать рекурсивную функцию, которая возвращает диагонали элементу ячейки с учетом индексов строк и столбцов ячейки. Мой алгоритм пока продвигается только к тому, чтобы диагональ шла в нижний правый угол 2D-списка, но я бы хотел, чтобы он получал все диагонали для любой позиции ячейки. rs cs являются ли индексы строк и столбцов ячейки, для которой мы хотим получить диагонали, и r c являются индексами текущей ячейки.

У меня есть общая идея, но я не могу разобраться в деталях. Прошло некоторое время с тех пор, как я углубился в рекурсию, и мне могла бы понадобиться помощь.

 #self is an instance of Board
def getDiag(self,rs,cs,r,s,lst=[],recCount=0):
 if recCount == 0:
    #boardList holds lists of BoardCell instances. Its attributes are irrelevant.
    lst.append[self.boardList[rs][cs]]
 else:
  lst.append[self.boardList[r][c]]

 if rs   1 < len(self.boardlist) and cs   1 < len(self.boardlist[0]):
    return self.getDiag(rs,cs,rs 1,rs 1,lst,recCount 1)
  

Главное, что нужно помнить при рекурсии, это то, что нам нужно решить

1. Когда остановиться
2. Как следующая рекурсия будет связана с текущей.

Теперь давайте разберем проблему.

• Если вам нужны диагонали из заданного квадрата, вам нужен этот квадрат плюс диагонали, идущие сверху справа, сверху слева, снизу справа и снизу слева от этого квадрата.
• Когда вы выпадаете из ребра ( rs < 0 , rs > row count , cs < 0 , cs > col count ), нам нужно остановить рекурсию.
• Для каждого другого квадрата верните себя плюс диагональ в соответствующем направлении

Вот некоторый код, который вернет индексы диагональных ячеек. Возврат значений диагональных ячеек является довольно тривиальным изменением по сравнению с этим:

 class Board:
    
    def __init__(self, r, c):
        self.boardRows = r
        self.boardCols = c

    def getDiag(self, rs, cs, direction='all'):
        
        if not 0 <= rs < self.boardRows or not 0 <= cs < self.boardCols:
            # fall off the edge
            return []
        
        if direction == 'all':
            return [[rs, cs]]   self.getDiag(rs - 1, cs   1, 'topright')   self.getDiag(rs - 1, cs - 1, 'topleft')   self.getDiag(rs   1, cs   1, 'bottomright')   self.getDiag(rs   1, cs - 1, 'bottomleft')
        
        # Just something to handle 'direction'
        if 'top' in direction: 
            delta_r = -1
        else:
            delta_r = 1
    
        if 'left' in direction: 
            delta_c = -1
        else:
            delta_c = 1
        
        # This square, plus the remaining diagonal in the correct direction.
        return [[rs, cs]]   self.getDiag(rs   delta_r, cs   delta_c, direction=direction)

    def printDiag(self, rs, cs, direction='all'):
        board = [["o"] * self.boardCols for i in range(self.boardRows)]
        diagCells = self.getDiag(rs, cs, direction)
        for i, j in diagCells:
            board[i][j] = u"u2022"
        
        board[rs][cs] = "*"
        
        print("-t"   "t".join(str(i) for i in range(self.boardCols)))
        print("n".join([f"{rownum}t"   "t".join(row) for rownum, row in enumerate(board)]))
  

Для проверки давайте напечатаем немаркированные квадраты как o , помеченные квадраты как • , а исходный квадрат как * :

 b = Board(5, 5)

# Middle diagonal
print(b.getDiag(2, 2))
b.printDiag(2, 2)
Output: 
[[2, 2], [1, 3], [0, 4], [1, 1], [0, 0], [3, 3], [4, 4], [3, 1], [4, 0]]
-   0   1   2   3   4
0   •   o   o   o   •
1   o   •   o   •   o
2   o   o   *   o   o
3   o   •   o   •   o
4   •   o   o   o   •


# Top-left diagonal
print(b.getDiag(0, 0))
b.printDiag(0, 0)
Output: 
[[0, 0], [1, 1], [2, 2], [3, 3], [4, 4]]
-   0   1   2   3   4
0   *   o   o   o   o
1   o   •   o   o   o
2   o   o   •   o   o
3   o   o   o   •   o
4   o   o   o   o   •

# Bottom-right diagonal
print(b.getDiag(4, 4))
b.printDiag(4, 4)
Output:
[[4, 4], [3, 3], [2, 2], [1, 1], [0, 0]]
-   0   1   2   3   4
0   •   o   o   o   o
1   o   •   o   o   o
2   o   o   •   o   o
3   o   o   o   •   o
4   o   o   o   o   *

# Top-right diagonal
print(b.getDiag(0, 4))
b.printDiag(0, 4)
Output:
[[0, 4], [1, 3], [2, 2], [3, 1], [4, 0]]
-   0   1   2   3   4
0   o   o   o   o   *
1   o   o   o   •   o
2   o   o   •   o   o
3   o   •   o   o   o
4   •   o   o   o   o

# Bottom-left diagonal
print(b.getDiag(4, 0))
b.printDiag(4, 0)
Output:
[[4, 0], [3, 1], [2, 2], [1, 3], [0, 4]]
-   0   1   2   3   4
0   o   o   o   o   •
1   o   o   o   •   o
2   o   o   •   o   o
3   o   •   o   o   o
4   *   o   o   o   o

# Top-edge diagonal
print(b.getDiag(0, 2))
b.printDiag(0, 2)
Output:
[[0, 2], [1, 3], [2, 4], [1, 1], [2, 0]]
-   0   1   2   3   4
0   o   o   *   o   o
1   o   •   o   •   o
2   •   o   o   o   •
3   o   o   o   o   o
4   o   o   o   o   o

# Right-edge diagonal
print(b.getDiag(2, 4))
b.printDiag(2, 4)
Output:
[[2, 4], [1, 3], [0, 2], [3, 3], [4, 2]]
-   0   1   2   3   4
0   o   o   •   o   o
1   o   o   o   •   o
2   o   o   o   o   *
3   o   o   o   •   o
4   o   o   •   o   o

# Bottom-edge diagonal
print(b.getDiag(4, 2))
b.printDiag(4, 2)
Output:
[[4, 2], [3, 3], [2, 4], [3, 1], [2, 0]]
-   0   1   2   3   4
0   o   o   o   o   o
1   o   o   o   o   o
2   •   o   o   o   •
3   o   •   o   •   o
4   o   o   *   o   o

# Left-edge diagonal
print(b.getDiag(2, 0))
b.printDiag(2, 0)
Output:
[[2, 0], [1, 1], [0, 2], [3, 1], [4, 2]]
-   0   1   2   3   4
0   o   o   •   o   o
1   o   •   o   o   o
2   *   o   o   o   o
3   o   •   o   o   o
4   o   o   •   o   o