NP困難な問題にぶつかっていないことを願っています！
これはNPの問題とはほど遠いです。
この問題を解決するための2つの異なるアプローチについて説明します。1つは期待どおりにフラッドフィルを使用し、もう1つは素集合データ構造を使用します。
フラッドフィル
N x M位置(row, column)が使用されていないときの行列がありnull、それ以外の場合は値が含まれているとします。
1..M行ごとに各列要素を調べる必要があります1..N。それは非常に簡単です：
for row in range(1, N + 1):
for column in range(1, M + 1):
if matrix[row][column] is not null:
floodfill(matrix, row, column)
値以外の値が見つかるたびにFloodFillアルゴリズムを呼び出す必要がありnullます。以下でFloodFillメソッドを定義すると、理由がより明確になります。
def floodfill(matrix, row, column):
# I will use a queue to keep record of the positions we are gonna traverse.
# Each element in the queue is a coordinate position (row,column) of an element
# of the matrix.
Q = Queue()
# A container for the up, down, left and right directions.
dirs = { (-1, 0), (1, 0), (0, -1), (0, 1) }
# Now we will add our initial position to the queue.
Q.push( (row, column) )
# And we will mark the element as null. You will definitely need to
# use a boolean matrix to mark visited elements. In this case I will simply
# mark them as null.
matrix[row][column] = null
# Go through each element in the queue, while there are still elements to visit.
while Q is not empty:
# Pop the next element to visit from the queue.
# Remember this is a (row, column) position.
(r, c) = Q.pop()
# Add the element to the output region.
region.add( (r, c) )
# Check for non-visited position adjacent to this (r,c) position.
# These are:
# (r + 1, c): down
# (r - 1, c): up
# (r, c - 1): left
# (r, c + 1): right
for (dr, dc) in dirs:
# Check if this adjacent position is not null and keep it between
# the matrix size.
if matrix[r + dr][c + dc] is not null
and r + dr <= rows(matrix)
and c + dc <= colums(matrix):
# Then add the position to the queue to be visited later
Q.push(r + dr, c + dc)
# And mark this position as visited.
matrix[r + dr][c + dc] = null
# When there are no more positions to visit. You can return the
# region visited.
return region
認識された領域の数を追跡している場合は、このアルゴリズムを変更して、各領域を異なる配列の指定された数でマークすることができます。再帰関数の代わりにキューを使用していることに気付くでしょう。これにより、再帰の上限に達するのを防ぐことができます。
ユニオン検索アルゴリズム
私がより高価だと考えたもう1つの解決策は、同じ目的を達成するために素集合データ構造を使用することです。floodfillメソッドの変更を示すだけです。
def floodfill(matrix):
disjoint_set = DisjointSet()
# Go through each row in the matrix
for row in range(1, N + 1):
# Go through each column in the matrix
for column in range(1, M + 1):
# Create a set for the current position
disjoint_set.makeSet(row, column)
if matrix[row - 1][column] is not null:
# If the position north of it it is not null then merge them
disjoint_set.merge((row, column), (row - 1, column))
if matrix[row][column - 1] is not null:
# If the position left of it it is not null then merge them
disjoint_set.merge((row, column), (row, column - 1))
# You can go through each position identifying its set and do something with it
for row in range(1, N + 1):
for column in range(1, M + 1):
regions[ disjoint_set.find(row, column) ] = (row, column)
return regions
これがお役に立てば幸いです。
あなたがそれを気にしなかったので、私は複雑さを示すことについて気にしませんでした。