如何在递归中处理计数

Question

import unittest

def riverSizes(test_input):
   l=[]
   river_sizes = 0
   for i in range(len(test_input)):
       for j in range(len(test_input[i])):
           if test_input[i][j] == 1:
               count = traverse_river(i, j, len(test_input), len(test_input[0]), test_input, 0)
               l.append(count)
               river_sizes += 1
   print(river_sizes,l)

def traverse_river(x, y, max_row, max_col, matrix, count):
    if x < 0 or x >= max_row or y < 0 or y >= max_col or matrix[x][y] != 1:
       return count
    matrix[x][y] = 2
    traverse_river(x - 1, y, max_row, max_col, matrix, count + 1)
    traverse_river(x + 1, y, max_row, max_col, matrix, count + 1)
    traverse_river(x, y + 1, max_row, max_col, matrix, count + 1)
    
class TestProgram(unittest.TestCase):
    def test_case_1(self):
       test_input = [[1, 0, 0, 1, 0], [1, 0, 1, 0, 0], [0, 0, 1, 0, 1], [1, 0, 1, 0, 1], [1, 0, 1, 1, 0]]
       expected = [1, 2, 2, 2, 5]
       riverSizes(test_input)
       self.assertEqual(sorted(riverSizes(test_input)), expected)

我正在尝试运行矩阵上的 dfs 并跟踪所有带有“1”的连接组件以及连接组件的长度计数。如何处理 recusrrsion

中的计数

Answer 1

代码的一些问题：

函数 riverSizes 没有 return 任何东西，因此对其应用 sorted 也无济于事。
递归也要考虑y - 1，因为有可能是U型，像这样的模式：
```
  1 0 1
  1 1 1
```
...而且您不想错过右上角的 1。
函数 traverse_river 并不总是 return 计数 -- 仅当第一个 if 条件为真时。

此外，您不需要：

将 count 作为参数传递。只需添加 returned 计数即可累积该值。
维护river_sizes，因为这是重复信息：它实际上等于len(l)。

这是它的工作原理：

def riverSizes(test_input):
   l = []
   for i in range(len(test_input)):
       for j in range(len(test_input[i])):
           if test_input[i][j] == 1:
               count = traverse_river(i, j, len(test_input), len(test_input[0]), test_input)
               l.append(count)
   return l

def traverse_river(x, y, max_row, max_col, matrix):
    if x < 0 or x >= max_row or y < 0 or y >= max_col or matrix[x][y] != 1:
       return 0
    matrix[x][y] = 2
    return (1 + traverse_river(x - 1, y, max_row, max_col, matrix)
              + traverse_river(x + 1, y, max_row, max_col, matrix)
              + traverse_river(x, y + 1, max_row, max_col, matrix)
              + traverse_river(x, y - 1, max_row, max_col, matrix))
    
test_input = [[1, 0, 0, 1, 0], [1, 0, 1, 0, 0], [0, 0, 1, 0, 1], [1, 0, 1, 0, 1], [1, 0, 1, 1, 0]]
print(riverSizes(test_input))

如何在递归中处理计数

How to handle count in recursion

python

graph

depth-first-search