資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究泛洪填充演算法
給定一個矩陣，該矩陣表示一個螢幕。螢幕的每個元素 (i, j) 被表示為一個畫素，該畫素的顏色用不同的數字標記。在此演算法中，當畫素已有選擇的先前的顏色時，該畫素將填充新的顏色。如果先前的顏色並不是先前的顏色，則將不會填充該畫素。在填充一個畫素之後，它將檢查其上、下、左、右畫素以執行相同的操作。
這個想法真的很簡單，首先，我們檢查選定的位置是否被先前的顏色填充，如果未被填充，演算法將不起作用。否則，它將用新顏色填充該畫素，並對其四個相鄰畫素進行遞迴。
輸入和輸出
Input: The screen matrix: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 2 2 2 2 0 1 0 1 1 1 2 2 0 1 0 1 1 1 2 2 2 2 0 1 1 1 1 1 2 1 1 1 1 1 1 1 2 2 1 Output: Screen matrix after flood fill 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 3 3 3 3 0 1 0 1 1 1 3 3 0 1 0 1 1 1 3 3 3 3 0 1 1 1 1 1 3 1 1 1 1 1 1 1 3 3 1
演算法
fillScreen(x, y, prevColor, newColor)
輸入：要開始的 (x,y) 座標、先前的顏色和新顏色。
輸出 −在可能的情況下，在將顏色從先前的顏色更改為新的顏色後，顯示螢幕。
Begin if (x, y) not in the screen range, then return if color of (x, y) ≠ prevColor, then return screen[x, y] := newColor fillScreen(x+1, y, prevColor, newColor) fillScreen(x-1, y, prevColor, newColor) fillScreen(x, y+1, prevColor, newColor) fillScreen(x, y-1, prevColor, newColor) End
示例
#include<iostream>
#define M 8
#define N 8
using namespace std;
int screen[M][N] = { //the screen dimention and colors
{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1}
};
void fillScreen(int x, int y, int prevColor, int newColor) { //replace previous color of (x,y), with new color
if (x < 0 || x >= M || y < 0 || y >= N) //when point exceeds the screen
return;
if (screen[x][y] != prevColor) //if the point(x,y) are not containing prevColor, do nothing
return;
screen[x][y] = newColor; //update the color
fillScreen(x+1, y, prevColor, newColor); //for the right of (x,y)
fillScreen(x-1, y, prevColor, newColor); //for the left of (x,y)
fillScreen(x, y+1, prevColor, newColor); //for the top of (x,y)
fillScreen(x, y-1, prevColor, newColor); //for the bottom of (x,y)
}
void floodFill(int x, int y, int newColor) {
int prevColor = screen[x][y]; //take the color before replacing with new color
fillScreen(x, y, prevColor, newColor);
}
int main() {
int x = 4, y = 4, newColor = 3;
cout << "Previous screen: "<< endl;
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++)
cout << screen[i][j] << " ";
cout << endl;
}
cout << endl;
floodFill(x, y, newColor); //start from (4, 4), with new color 3
cout << "Updated screen: "<< endl;
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++)
cout << screen[i][j] << " ";
cout << endl;
}
}輸出
Previous screen 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 2 2 2 2 0 1 0 1 1 1 2 2 0 1 0 1 1 1 2 2 2 2 0 1 1 1 1 1 2 1 1 1 1 1 1 1 2 2 1 Updated screen: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 3 3 3 3 0 1 0 1 1 1 3 3 0 1 0 1 1 1 3 3 3 3 0 1 1 1 1 1 3 1 1 1 1 1 1 1 3 3 1
更新於： 17-6 月-2020
1 千次瀏覽
廣告