フラッドフィルアルゴリズム
フラッドフィル(シードフィルとも呼ばれます)は、多次元アレイ内の特定のノードに接続されている領域を決定するアルゴリズムです。
これは、ペイントプログラムの「バケツ」塗りつぶしツールで使用され、接続された同様の色の領域を異なる色で塗りつぶします。また、囲碁やマインスイーパなどのゲームでは、どの部分をクリアするかを決定します。特定の境界領域を色で塗りつぶすために画像に適用すると、境界塗りつぶしとも呼ばれます。
塗りつぶしアルゴリズムは、開始ノード、ターゲットカラー、および置換カラーの3つのパラメーターを取ります。
左側の次の行列を検討してください–開始ノードが (3, 9)、ターゲットカラーは “BLACK” 交換色は “GREY”、アルゴリズムは、ターゲットカラーのパスによって開始ノードに接続されているマトリックス内のすべてのノードを検索し、それらを置換カラーに変更します。
行列の各セルは1つのピクセルを表すことに注意してください。
アプローチ1:(BFSを使用)
A queueを使用したベースの実装 幅優先探索(BFS) 以下に擬似コードで示します。
- 空のQueueを作成します。
- 開始ピクセルをキューに入れ、処理済みとしてマークします。
-
Queueが空になるまでループします
- フロントノードをデキューして処理します。
- 現在のピクセル(ポップされたノード)の色を置換の色に置き換えます。
- 現在のピクセルの隣接する8つのピクセルすべてを処理し、現在のピクセルと同じ色の有効な各ピクセルをキューに入れます。
アルゴリズムは、C++、Java、およびPythonで次のように実装できます。
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
#include <iostream> #include <queue> #include <iomanip> using namespace std; //以下のアレイは、8つの可能なすべての動きの詳細を示しています int row[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int col[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; //からピクセル(x, y)に移動できるかどうかを確認します //現在のピクセル。ピクセルの場合、関数はfalseを返します //色が異なるか、有効なピクセルではありません bool isSafe(vector<vector<char>> const &mat, int x, int y, char target) { return (x >= 0 && x < mat.size()) && (y >= 0 && y < mat[0].size()) && mat[x][y] == target; } //BFSを使用したフラッドフィル void floodfill(vector<vector<char>> &mat, int x, int y, char replacement) { // 規範事例 if (mat.size() == 0) { return; } //キューを作成し、開始ピクセルをエンキューします queue<pair<int, int>> q; q.push({x, y}); //ターゲットカラーを取得します char target = mat[x][y]; //ターゲットの色は置換と同じです if (target == replacement) { return; } //Queueが空になると中断します while (!q.empty()) { //フロントノードをデキューして処理します pair<int, int> node = q.front(); q.pop(); //(x, y)は現在のピクセルを表します int x = node.first, y = node.second; //現在のピクセルの色を置換の色に置き換えます mat[x][y] = replacement; //現在のピクセルの隣接する8つのピクセルすべてを処理し、 //各有効なピクセルをキューに入れます for (int k = 0; k < 8; k++) { //位置(x + row[k]、y + col[k])の隣接ピクセルが //有効で、現在のピクセルと同じ色です if (isSafe(mat, x + row[k], y + col[k], target)) { //隣接するピクセルをキューに入れます q.push({x + row[k], y + col[k]}); } } } } //行列を出力するユーティリティ関数 void printMatrix(vector<vector<char>> const &mat) { for (int i = 0; i < mat.size(); i++) { for (int j = 0; j < mat[0].size(); j++) { cout << setw(3) << mat[i][j]; } cout << endl; } } int main() { //異なる色の画面の一部を示すマトリックス vector<vector<char>> mat = { { 'Y', 'Y', 'Y', 'G', 'G', 'G', 'G', 'G', 'G', 'G' }, { 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'G', 'X', 'X', 'X' }, { 'G', 'G', 'G', 'G', 'G', 'G', 'G', 'X', 'X', 'X' }, { 'W', 'W', 'W', 'W', 'W', 'G', 'G', 'G', 'G', 'X' }, { 'W', 'R', 'R', 'R', 'R', 'R', 'G', 'X', 'X', 'X' }, { 'W', 'W', 'W', 'R', 'R', 'G', 'G', 'X', 'X', 'X' }, { 'W', 'B', 'W', 'R', 'R', 'R', 'R', 'R', 'R', 'X' }, { 'W', 'B', 'B', 'B', 'B', 'R', 'R', 'X', 'X', 'X' }, { 'W', 'B', 'B', 'X', 'B', 'B', 'B', 'B', 'X', 'X' }, { 'W', 'B', 'B', 'X', 'X', 'X', 'X', 'X', 'X', 'X' } }; //ノードを開始します int x = 3, y = 9; //ターゲットカラー`X`を持つ //置換色 char replacement = 'C'; //ターゲットカラーを置換カラーに置き換えます floodfill(mat, x, y, replacement); //置換後に色を印刷します printMatrix(mat); return 0; } |
出力:
Y Y Y G G G G G G G
Y Y Y Y Y Y G C C C
G G G G G G G C C C
W W W W W G G G G C
W R R R R R G C C C
W W W R R G G C C C
W B W R R R R R R C
W B B B B R R C C C
W B B C B B B B C C
W B B C C C C C C C
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 |
import java.util.ArrayDeque; import java.util.Arrays; import java.util.Queue; class Pair { int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } } class Main { //以下のアレイは、8つの可能なすべての動きの詳細を示しています private static final int[] row = { -1, -1, -1, 0, 0, 1, 1, 1 }; private static final int[] col = { -1, 0, 1, -1, 1, -1, 0, 1 }; //からピクセル(x, y)に移動できるかどうかを確認します //現在のピクセル。ピクセルの場合、関数はfalseを返します //色が異なるか、有効なピクセルではありません public static boolean isSafe(char[][] mat, int x, int y, char target) { return x >= 0 && x < mat.length && y >= 0 && y < mat[0].length && mat[x][y] == target; } //BFSを使用したフラッドフィル public static void floodfill(char[][] mat, int x, int y, char replacement) { // 規範事例 if (mat == null || mat.length == 0) { return; } //キューを作成し、開始ピクセルをエンキューします Queue<Pair> q = new ArrayDeque<>(); q.add(new Pair(x, y)); //ターゲットカラーを取得します char target = mat[x][y]; //ターゲットの色は置換と同じです if (target == replacement) { return; } //Queueが空になると中断します while (!q.isEmpty()) { //フロントノードをデキューして処理します Pair node = q.poll(); //(x, y)は現在のピクセルを表します x = node.x; y = node.y; //現在のピクセルの色を置換の色に置き換えます mat[x][y] = replacement; //現在のピクセルの隣接する8つのピクセルすべてを処理し、 //各有効なピクセルをキューに入れます for (int k = 0; k < row.length; k++) { //位置(x + row[k]、y + col[k])の隣接ピクセルが //有効で、現在のピクセルと同じ色です if (isSafe(mat,x + row[k], y + col[k], target)) { //隣接するピクセルをキューに入れます q.add(new Pair(x + row[k], y + col[k])); } } } } public static void main(String[] args) { //異なる色の画面の一部を示すマトリックス char[][] mat = { "YYYGGGGGGG".toCharArray(), "YYYYYYGXXX".toCharArray(), "GGGGGGGXXX".toCharArray(), "WWWWWGGGGX".toCharArray(), "WRRRRRGXXX".toCharArray(), "WWWRRGGXXX".toCharArray(), "WBWRRRRRRX".toCharArray(), "WBBBBRRXXX".toCharArray(), "WBBXBBBBXX".toCharArray(), "WBBXXXXXXX".toCharArray() }; //ノードを開始します int x = 3, y = 9; //ターゲットカラー`X`を持つ //置換色 char replacement = 'C'; //ターゲットカラーを置換カラーに置き換えます floodfill(mat, x, y, replacement); //置換後に色を印刷します for (char[] row: mat) { System.out.println(Arrays.toString(row)); } } } |
出力:
[Y, Y, Y, G, G, G, G, G, G, G]
[Y, Y, Y, Y, Y, Y, G, C, C, C]
[G, G, G, G, G, G, G, C, C, C]
[W, W, W, W, W, G, G, G, G, C]
[W, R, R, R, R, R, G, C, C, C]
[W, W, W, R, R, G, G, C, C, C]
[W, B, W, R, R, R, R, R, R, C]
[W, B, B, B, B, R, R, C, C, C]
[W, B, B, C, B, B, B, B, C, C]
[W, B, B, C, C, C, C, C, C, C]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
from collections import deque #以下に、考えられる8つの動きすべての詳細を示します。 row = [-1, -1, -1, 0, 0, 1, 1, 1] col = [-1, 0, 1, -1, 1, -1, 0, 1] ＃からピクセル(x, y)に移動できるかどうかを確認します #の現在のピクセル。ピクセルの場合、関数はfalseを返します #の色が異なるか、有効なピクセルではありません def isSafe(mat, x, y, target): return 0 <= x < len(mat) and 0 <= y < len(mat[0]) and mat[x][y] == target #BFSを使用したフラッドフィル def floodfill(mat, x, y, replacement): #ベースケース if not mat or not len(mat): return #はキューを作成し、開始ピクセルをエンキューします q = deque() q.append((x, y)) #はターゲットカラーを取得します target = mat[x][y] #のターゲットカラーは交換と同じです if target == replacement: return # Queueが空になると#が中断します while q: #はフロントノードをデキューして処理します x, y = q.popleft() #は、現在のピクセルの色を置換の色に置き換えます mat[x][y] = replacement #は、現在のピクセルの隣接する8つのピクセルすべてを処理します。 #は各有効なピクセルをエンキューします for k in range(len(row)): #(x + row[k]、y + col[k])の位置にある隣接ピクセルが #は有効で、現在のピクセルと同じ色です if isSafe(mat, x + row[k], y + col[k], target): #は隣接するピクセルをエンキューします q.append((x + row[k], y + col[k])) if __name__ == '__main__': # 異なる色の画面の一部を示す#マトリックス mat = [ ['Y', 'Y', 'Y', 'G', 'G', 'G', 'G', 'G', 'G', 'G'], ['Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'G', 'X', 'X', 'X'], ['G', 'G', 'G', 'G', 'G', 'G', 'G', 'X', 'X', 'X'], ['W', 'W', 'W', 'W', 'W', 'G', 'G', 'G', 'G', 'X'], ['W', 'R', 'R', 'R', 'R', 'R', 'G', 'X', 'X', 'X'], ['W', 'W', 'W', 'R', 'R', 'G', 'G', 'X', 'X', 'X'], ['W', 'B', 'W', 'R', 'R', 'R', 'R', 'R', 'R', 'X'], ['W', 'B', 'B', 'B', 'B', 'R', 'R', 'X', 'X', 'X'], ['W', 'B', 'B', 'X', 'B', 'B', 'B', 'B', 'X', 'X'], ['W', 'B', 'B', 'X', 'X', 'X', 'X', 'X', 'X', 'X'] ] #開始ノード x = 3 y = 9 # ターゲットカラー`X`の #交換色 replacement = 'C' #はターゲットカラーを置換カラーに置き換えます floodfill(mat, x, y, replacement) #は交換後の色を印刷します for r in mat: print(r) |
出力:
[‘Y’, ‘Y’, ‘Y’, ‘G’, ‘G’, ‘G’, ‘G’, ‘G’, ‘G’, ‘G’]
[‘Y’, ‘Y’, ‘Y’, ‘Y’, ‘Y’, ‘Y’, ‘G’, ‘C’, ‘C’, ‘C’]
[‘G’, ‘G’, ‘G’, ‘G’, ‘G’, ‘G’, ‘G’, ‘C’, ‘C’, ‘C’]
[‘W’, ‘W’, ‘W’, ‘W’, ‘W’, ‘G’, ‘G’, ‘G’, ‘G’, ‘C’]
[‘W’, ‘R’, ‘R’, ‘R’, ‘R’, ‘R’, ‘G’, ‘C’, ‘C’, ‘C’]
[‘W’, ‘W’, ‘W’, ‘R’, ‘R’, ‘G’, ‘G’, ‘C’, ‘C’, ‘C’]
[‘W’, ‘B’, ‘W’, ‘R’, ‘R’, ‘R’, ‘R’, ‘R’, ‘R’, ‘C’]
[‘W’, ‘B’, ‘B’, ‘B’, ‘B’, ‘R’, ‘R’, ‘C’, ‘C’, ‘C’]
[‘W’, ‘B’, ‘B’, ‘C’, ‘B’, ‘B’, ‘B’, ‘B’, ‘C’, ‘C’]
[‘W’, ‘B’, ‘B’, ‘C’, ‘C’, ‘C’, ‘C’, ‘C’, ‘C’, ‘C’]
提案されたソリューションの時間計算量は O(M × N) とが必要です O(M × N) 余分なスペース、ここで M と N 行列の次元です。
アプローチ2:(DFSを使用)
使用できます 深さ優先探索(DFS) この問題を解決するために。アイデアは、マトリックス内のソースノードから開始し、その色を置換色に置き換え、有効な8つの隣接するピクセルすべてを再帰的にに探索し、それらの色を置き換えることです。処理されたすべてのノードの色を置き換えるため、ここでは訪問されたアレイは必要ありません。また、色が異なるため、次回は考慮されません。
アルゴリズムは、C++、Java、およびPythonで次のように実装できます。
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <iostream> #include <vector> #include <iomanip> using namespace std; //以下のアレイは、8つの可能なすべての動きの詳細を示しています int row[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int col[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; //からピクセル(x, y)に移動できるかどうかを確認します //現在のピクセル。ピクセルの場合、関数はfalseを返します //色が異なるか、有効なピクセルではありません bool isSafe(vector<vector<char>> const &mat, int x, int y, char target) { return (x >= 0 && x < mat.size()) && (y >= 0 && y < mat[0].size()) && mat[x][y] == target; } //DFSを使用したフラッドフィル void floodfill(vector<vector<char>> &mat, int x, int y, char replacement) { // 規範事例 if (mat.size() == 0) { return; } //ターゲットカラーを取得します char target = mat[x][y]; //ターゲットの色は置換と同じです if (target == replacement) { return; } //現在のピクセルの色を置換の色に置き換えます mat[x][y] = replacement; //現在のピクセルの隣接する8つのピクセルすべてを処理し、 //有効なピクセルごとに繰り返します for (int k = 0; k < 8; k++) { //位置(x + row[k]、y + col[k])の隣接ピクセルが //有効なピクセルで、現在のピクセルと同じ色です if (isSafe(mat, x + row[k], y + col[k], target)) { floodfill(mat, x + row[k], y + col[k], replacement); } } } //行列を出力するユーティリティ関数 void printMatrix(vector<vector<char>> const &mat) { for (int i = 0; i < mat.size(); i++) { for (int j = 0; j < mat[0].size(); j++) { cout << setw(3) << mat[i][j]; } cout << endl; } } int main() { //異なる色の画面の一部を示すマトリックス vector<vector<char>> mat = { { 'Y', 'Y', 'Y', 'G', 'G', 'G', 'G', 'G', 'G', 'G' }, { 'Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'G', 'X', 'X', 'X' }, { 'G', 'G', 'G', 'G', 'G', 'G', 'G', 'X', 'X', 'X' }, { 'W', 'W', 'W', 'W', 'W', 'G', 'G', 'G', 'G', 'X' }, { 'W', 'R', 'R', 'R', 'R', 'R', 'G', 'X', 'X', 'X' }, { 'W', 'W', 'W', 'R', 'R', 'G', 'G', 'X', 'X', 'X' }, { 'W', 'B', 'W', 'R', 'R', 'R', 'R', 'R', 'R', 'X' }, { 'W', 'B', 'B', 'B', 'B', 'R', 'R', 'X', 'X', 'X' }, { 'W', 'B', 'B', 'X', 'B', 'B', 'B', 'B', 'X', 'X' }, { 'W', 'B', 'B', 'X', 'X', 'X', 'X', 'X', 'X', 'X' } }; //ノードを開始します int x = 3, y = 9; //ターゲットカラー`X`を持つ //置換色 char replacement = 'C'; //DFSを使用してターゲットカラーを置換カラーに置き換えます floodfill(mat, x, y, replacement); //置換後に色を印刷します printMatrix(mat); return 0; } |
出力:
Y Y Y G G G G G G G
Y Y Y Y Y Y G C C C
G G G G G G G C C C
W W W W W G G G G C
W R R R R R G C C C
W W W R R G G C C C
W B W R R R R R R C
W B B B B R R C C C
W B B C B B B B C C
W B B C C C C C C C
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
import java.util.Arrays; class Main { //以下のアレイは、8つの可能なすべての動きの詳細を示しています private static final int[] row = { -1, -1, -1, 0, 0, 1, 1, 1 }; private static final int[] col = { -1, 0, 1, -1, 1, -1, 0, 1 }; //からピクセル(x, y)に移動できるかどうかを確認します //現在のピクセル。ピクセルの場合、関数はfalseを返します //色が異なるか、有効なピクセルではありません public static boolean isSafe(char[][] mat, int x, int y, char target) { return x >= 0 && x < mat.length && y >= 0 && y < mat[0].length && mat[x][y] == target; } public static void floodfill(char[][] mat, int x, int y, char replacement) { // 規範事例 if (mat == null || mat.length == 0) { return; } //ターゲットカラーを取得します char target = mat[x][y]; //ターゲットの色は置換と同じです if (target == replacement) { return; } //現在のピクセルの色を置換の色に置き換えます mat[x][y] = replacement; //現在のピクセルの隣接する8つのピクセルすべてを処理し、 //有効なピクセルごとに繰り返します for (int k = 0; k < row.length; k++) { //位置(x + row[k]、y + col[k])の隣接ピクセルが //有効なピクセルで、現在のピクセルと同じ色です if (isSafe(mat, x + row[k], y + col[k], target)) { floodfill(mat, x + row[k], y + col[k], replacement); } } } public static void main(String[] args) { //異なる色の画面の一部を示すマトリックス char[][] mat = { "YYYGGGGGGG".toCharArray(), "YYYYYYGXXX".toCharArray(), "GGGGGGGXXX".toCharArray(), "WWWWWGGGGX".toCharArray(), "WRRRRRGXXX".toCharArray(), "WWWRRGGXXX".toCharArray(), "WBWRRRRRRX".toCharArray(), "WBBBBRRXXX".toCharArray(), "WBBXBBBBXX".toCharArray(), "WBBXXXXXXX".toCharArray() }; //ノードを開始します int x = 3, y = 9; //ターゲットカラー`X`を持つ //置換色 char replacement = 'C'; //DFSを使用してターゲットカラーを置換カラーに置き換えます floodfill(mat, x, y, replacement); //置換後に色を印刷します for (char[] row: mat) { System.out.println(Arrays.toString(row)); } } } |
出力:
[Y, Y, Y, G, G, G, G, G, G, G]
[Y, Y, Y, Y, Y, Y, G, C, C, C]
[G, G, G, G, G, G, G, C, C, C]
[W, W, W, W, W, G, G, G, G, C]
[W, R, R, R, R, R, G, C, C, C]
[W, W, W, R, R, G, G, C, C, C]
[W, B, W, R, R, R, R, R, R, C]
[W, B, B, B, B, R, R, C, C, C]
[W, B, B, C, B, B, B, B, C, C]
[W, B, B, C, C, C, C, C, C, C]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#以下に、考えられる8つの動きすべての詳細を示します。 row = [-1, -1, -1, 0, 0, 1, 1, 1] col = [-1, 0, 1, -1, 1, -1, 0, 1] ＃からピクセル(x, y)に移動できるかどうかを確認します #の現在のピクセル。ピクセルの場合、関数はfalseを返します #の色が異なるか、有効なピクセルではありません def isSafe(mat, x, y, target): return 0 <= x < len(mat) and 0 <= y < len(mat[0]) and mat[x][y] == target # DFSを使用した#フラッドフィル def floodfill(mat, x, y, replacement): #ベースケース if not mat or not len(mat): return #はターゲットカラーを取得します target = mat[x][y] #のターゲットカラーは交換と同じです if target == replacement: return #は、現在のピクセルの色を置換の色に置き換えます mat[x][y] = replacement #は、現在のピクセルの隣接する8つのピクセルすべてを処理します。 # 有効なピクセルごとに#が繰り返されます for k in range(len(row)): #(x + row[k]、y + col[k])の位置にある隣接ピクセルが #は有効なピクセルであり、現在のピクセルと同じ色です。 if isSafe(mat, x + row[k], y + col[k], target): floodfill(mat, x + row[k], y + col[k], replacement) if __name__ == '__main__': # 異なる色の画面の一部を示す#マトリックス mat = [ ['Y', 'Y', 'Y', 'G', 'G', 'G', 'G', 'G', 'G', 'G'], ['Y', 'Y', 'Y', 'Y', 'Y', 'Y', 'G', 'X', 'X', 'X'], ['G', 'G', 'G', 'G', 'G', 'G', 'G', 'X', 'X', 'X'], ['W', 'W', 'W', 'W', 'W', 'G', 'G', 'G', 'G', 'X'], ['W', 'R', 'R', 'R', 'R', 'R', 'G', 'X', 'X', 'X'], ['W', 'W', 'W', 'R', 'R', 'G', 'G', 'X', 'X', 'X'], ['W', 'B', 'W', 'R', 'R', 'R', 'R', 'R', 'R', 'X'], ['W', 'B', 'B', 'B', 'B', 'R', 'R', 'X', 'X', 'X'], ['W', 'B', 'B', 'X', 'B', 'B', 'B', 'B', 'X', 'X'], ['W', 'B', 'B', 'X', 'X', 'X', 'X', 'X', 'X', 'X'] ] #開始ノード x, y = (3, 9) # 目標色`X`を持つ #交換色 replacement = 'C' #は、DFSを使用してターゲットカラーを置換カラーに置き換えます floodfill(mat, x, y, replacement) #は交換後の色を印刷します for r in mat: print(r) |
出力:
[‘Y’, ‘Y’, ‘Y’, ‘G’, ‘G’, ‘G’, ‘G’, ‘G’, ‘G’, ‘G’]
[‘Y’, ‘Y’, ‘Y’, ‘Y’, ‘Y’, ‘Y’, ‘G’, ‘C’, ‘C’, ‘C’]
[‘G’, ‘G’, ‘G’, ‘G’, ‘G’, ‘G’, ‘G’, ‘C’, ‘C’, ‘C’]
[‘W’, ‘W’, ‘W’, ‘W’, ‘W’, ‘G’, ‘G’, ‘G’, ‘G’, ‘C’]
[‘W’, ‘R’, ‘R’, ‘R’, ‘R’, ‘R’, ‘G’, ‘C’, ‘C’, ‘C’]
[‘W’, ‘W’, ‘W’, ‘R’, ‘R’, ‘G’, ‘G’, ‘C’, ‘C’, ‘C’]
[‘W’, ‘B’, ‘W’, ‘R’, ‘R’, ‘R’, ‘R’, ‘R’, ‘R’, ‘C’]
[‘W’, ‘B’, ‘B’, ‘B’, ‘B’, ‘R’, ‘R’, ‘C’, ‘C’, ‘C’]
[‘W’, ‘B’, ‘B’, ‘C’, ‘B’, ‘B’, ‘B’, ‘B’, ‘C’, ‘C’]
[‘W’, ‘B’, ‘B’, ‘C’, ‘C’, ‘C’, ‘C’, ‘C’, ‘C’, ‘C’]
提案されたソリューションの時間計算量は O(M × N) とが必要です O(M × N) 余分なスペース、ここで M と N 行列の次元です。
参照： フラッドフィル–ウィキペディア