資料結構
網路
RDBMS
作業系統
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 千次+ 瀏覽
廣告