回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>我试图在一个二维二进制矩阵中计算岛的数目(一组相连的1形成一个岛)。在</p>
<p>示例:</p>
<pre><code>[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
]
</code></pre>
<p>在上述矩阵中,有5个岛屿,分别是:</p>
^{pr2}$
<p>为了计算二维矩阵中的岛数,我假设矩阵是一个图,然后使用DFS算法来计算岛数。在</p>
<p>我跟踪DFS(递归函数)调用的数量,因为图中会有许多组件。在</p>
<p>下面是我为此编写的代码:</p>
<pre><code># count the 1's in the island
def count_houses(mat, visited, i, j):
# base case
if i < 0 or i >= len(mat) or j < 0 or j >= len(mat[0]) or\
visited[i][j] is True or mat[i][j] == 0:
return 0
# marking visited at i, j
visited[i][j] = True
# cnt is initialized to 1 coz 1 is found
cnt = 1
# now go in all possible directions (i.e. form 8 branches)
# starting from the left upper corner of i,j and going down to right bottom
# corner of i,j
for r in xrange(i-1, i+2, 1):
for c in xrange(j-1, j+2, 1):
# print 'r:', r
# print 'c:', c
# don't call for i, j
if r != i and c != j:
cnt += count_houses(mat, visited, r, c)
return cnt
def island_count(mat):
houses = list()
clusters = 0
row = len(mat)
col = len(mat[0])
# initialize the visited matrix
visited = [[False for i in xrange(col)] for j in xrange(row)]
# run over matrix, search for 1 and then do dfs when found 1
for i in xrange(row):
for j in xrange(col):
# see if value at i, j is 1 in mat and val at i, j is False in
# visited
if mat[i][j] == 1 and visited[i][j] is False:
clusters += 1
h = count_houses(mat, visited, i, j)
houses.<a href="https://www.cnpython.com/list/append" class="inner-link">append</a>(h)
print 'clusters:', clusters
return houses
if __name__ == '__main__':
mat = [
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
]
houses = island_count(mat)
print houses
# print 'maximum houses:', max(houses)
</code></pre>
<p>我在参数中传递的矩阵的输出错误。我得到了<code>7</code>,但是有{<cd2>}簇。在</p>
<p>我试着调试代码中的任何逻辑错误。但我找不到问题出在哪里。在</p>