漫水填充也叫泛洪填充，是画图软件中的油漆桶功能，但在运用中，远不止于此，比如构造一个矩阵数据，需要检测边界，在边界的内外填入不同的数据。油漆桶是对图形的快速填充，将图象以位图数据的形式来看，其实也是一个矩阵数据或者说是二维数组，所以我们如果以数字作为矩阵数据，那么只需检测里面的数据即可。然后将数据再绘制成图像，那就是油漆桶的功能。为了保存数据，我们定义了一个数字矩阵，并在矩阵中实现相应的填充方法，代码如下。
#region DigitMatrix ////// 数字矩阵 /// public class DigitMatrix { #region 属性 ////// 行数 /// public int RowCount { get; private set; } ////// 列数 /// public int ColumnCount { get; private set; } public int[,] Data { get; private set; } #endregion public DigitMatrix(int rowCount, int columnCount) { RowCount = rowCount; ColumnCount = columnCount; Data = new int[RowCount, ColumnCount]; } public override string ToString() { StringBuilder sb = new StringBuilder(); for (int r = 0; r < RowCount; r++) { string line = ""; for (int c = 0; c < ColumnCount; c++) { line += Data[r, c]; } sb.AppendLine(line); } return sb.ToString(); } #region FloodFill8 ////// 漫水填充(8邻域填充) /// /// 行 /// 列 /// /// /// public void FloodFill8(int r, int c, int newValue, int oldValue) {//递归实现可能造成堆栈溢出错误 if (r >= 0 && r < RowCount && c >= 0 && c < ColumnCount && Data[r, c] == oldValue && Data[r, c] != newValue) { Data[r, c] = newValue; FloodFill8(r + 1, c, newValue, oldValue); FloodFill8(r - 1, c, newValue, oldValue); FloodFill8(r, c + 1, newValue, oldValue); FloodFill8(r, c - 1, newValue, oldValue); FloodFill8(r + 1, c + 1, newValue, oldValue); FloodFill8(r - 1, c - 1, newValue, oldValue); FloodFill8(r - 1, c + 1, newValue, oldValue); FloodFill8(r + 1, c - 1, newValue, oldValue); } } #endregion #region FloodFill8WithStack ////// 漫水填充(基于堆的8邻域填充) /// /// 行 /// 列 /// /// /// public void FloodFill8WithStack(int r, int c, int newValue, int oldValue) { var stackRow = new Stack (); var stackColumn = new Stack (); stackRow.Push(r); stackColumn.Push(c); bool CheckNewSeed(int r1, int c1) { if (r1 >= 0 && r1 < RowCount && c1 >= 0 && c1 < ColumnCount && Data[r1, c1] == oldValue && Data[r1, c1] != newValue) { Data[r1, c1] = newValue; stackRow.Push(r1); stackColumn.Push(c1); return true; } return false; } while (true) { if (stackRow.Count <= 0) { break; } r = stackRow.Pop(); c = stackColumn.Pop(); CheckNewSeed(r, c); CheckNewSeed(r + 1, c); CheckNewSeed(r - 1, c); CheckNewSeed(r, c + 1); CheckNewSeed(r, c - 1); CheckNewSeed(r + 1, c + 1); CheckNewSeed(r - 1, c - 1); CheckNewSeed(r - 1, c + 1); CheckNewSeed(r + 1, c - 1); } } #endregion #region FloodFill4 ////// 漫水填充(4邻域填充) /// /// 行 /// 列 /// /// public void FloodFill4(int r, int c, int newValue, int oldValue) {//递归实现可能造成堆栈溢出错误 if (r >= 0 && r < RowCount && c >= 0 && c < ColumnCount && Data[r, c] == oldValue && Data[r, c] != newValue) { Data[r, c] = newValue; FloodFill4(r + 1, c, newValue, oldValue); FloodFill4(r - 1, c, newValue, oldValue); FloodFill4(r, c + 1, newValue, oldValue); FloodFill4(r, c - 1, newValue, oldValue); } } #endregion #region FloodFill4WithStack ////// 漫水填充(基于堆的4邻域填充) /// /// 行 /// 列 /// /// public void FloodFill4WithStack(int r, int c, int newValue, int oldValue) { var stackRow = new Stack (); var stackColumn = new Stack (); stackRow.Push(r); stackColumn.Push(c); bool CheckNewSeed(int r1, int c1) { if (r1 >= 0 && r1 < RowCount && c1 >= 0 && c1 < ColumnCount && Data[r1, c1] == oldValue && Data[r1, c1] != newValue) { Data[r1, c1] = newValue; stackRow.Push(r1); stackColumn.Push(c1); return true; } return false; } while (true) { if (stackRow.Count <= 0) { break; } r = stackRow.Pop(); c = stackColumn.Pop(); CheckNewSeed(r, c); CheckNewSeed(r + 1, c); CheckNewSeed(r - 1, c); CheckNewSeed(r, c + 1); CheckNewSeed(r, c - 1); } } #endregion #region FloodFillScanRowColumn ////// 漫水填充(基于行扫描行列的递归填充) /// /// 行 /// 列 /// /// public void FloodFillScanRowColumn(int r, int c, int newValue, int oldValue) {//递归实现可能造成堆栈溢出错误 if (oldValue == newValue) return; if (Data[r, c] != oldValue) return; int c1; //从当前位置扫描至最右边 c1 = c; while (c1 < ColumnCount && Data[r, c1] == oldValue) { Data[r, c1] = newValue; c1++; } //从当前位置扫描至最左边 c1 = c - 1; while (c1 >= 0 && Data[r, c1] == oldValue) { Data[r, c1] = newValue; c1--; } //向上检测新的扫描行 c1 = c; while (c1 < ColumnCount && Data[r, c1] == newValue) { if (r > 0 && Data[r - 1, c1] == oldValue) { FloodFillScanRowColumn(r - 1, c1, newValue, oldValue); } c1++; } c1 = c - 1; while (c1 >= 0 && Data[r, c1] == newValue) { if (r > 0 && Data[r - 1, c1] == oldValue) { FloodFillScanRowColumn(r - 1, c1, newValue, oldValue); } c1--; } //向下检测新的扫描行 c1 = c; while (c1 < ColumnCount && Data[r, c1] == newValue) { if (r < RowCount - 1 && Data[r + 1, c1] == oldValue) { FloodFillScanRowColumn(r + 1, c1, newValue, oldValue); } c1++; } c1 = c - 1; while (c1 >= 0 && Data[r, c1] == newValue) { if (r < RowCount - 1 && Data[r + 1, c1] == oldValue) { FloodFillScanRowColumn(r + 1, c1, newValue, oldValue); } c1--; } //由于检测到新的行之后会递归检测，所以所有的空间都将被检测到。 } #endregion #region FloodFillScanRowColumnWithStack ////// 漫水填充(基于堆的扫描行列的填充) /// /// 行 /// 列 /// /// public void FloodFillScanRowColumnWithStack(int r, int c, int newValue, int oldValue) { if (oldValue == newValue) { Console.WriteLine("区域已经填充，不需要处理。"); return; } var stackRow = new Stack (); var stackColumn = new Stack (); int c1; bool spanBottom;//检测下方 bool spanTop;//检测上方 stackRow.Push(r); stackColumn.Push(c); try { while (true) { r = (stackRow.Count > 0 ? stackRow.Pop() : -1); if (r == -1) return; c = (stackColumn.Count > 0 ? stackColumn.Pop() : -1); c1 = c; while (c1 >= 0 && Data[r, c1] == oldValue) c1--; // 跳到需填充的最左位置. c1++; //向右 spanBottom = spanTop = false; while (c1 < ColumnCount && Data[r, c1] == oldValue)//向上扫描到需要填充的位置 { Data[r, c1] = newValue;//填充数据 if (!spanBottom && r > 0 && Data[r - 1, c1] == oldValue)//没有在检测下方，而下方有需要填充的位置，将位置压入到堆栈中，然后跳过该行. { stackRow.Push(r - 1); stackColumn.Push(c1); spanBottom = true; } else if (spanBottom && r > 0 && Data[r - 1, c1] != oldValue)//检测下方，向上扫描到边界，则不再检测底边。 { spanBottom = false; } if (!spanTop && r < RowCount - 1 && Data[r + 1, c1] == oldValue) //没有在检测上方， 而上方有需要填充的位置，将位置压入到堆栈中，然后跳过该行. { stackRow.Push(r + 1); stackColumn.Push(c1); spanTop = true; } else if (spanTop && r < RowCount - 1 && Data[r + 1, c1] != oldValue)//检测上方，向上扫描到边界，则不再检测上方。 { spanTop = false; } c1++;//向右扫描 } } } catch (Exception ex) { Console.WriteLine($"{r}行,{c}列;{ex.Message}"); } } #endregion } #endregion
边界数据直接填写到DigitMatrix中，然后调用 matrix.FloodFillScanRowColumnWithStack(0, 0, 2, 0);，其中2是newValue，0是oldValue。
实现后的效果图
红色区为填充部分，黑色为图形的边界，白色部分是图形的内部。
参考文章