完善程序2解析

 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

/**************************************************************** 
 * Description: floor fill 泛洪填图
 * Author: Alex Li
 * Date: 2023-08-16 15:45:02
 * LastEditTime: 2023-09-13 06:21:04
****************************************************************/
#include<iostream>
#include<queue>
using namespace std;

const int ROWS = 8;
const int COLS = 8;

struct Point {
    int r, c;
    Point(int r, int c): r(r), c(c) {}//初始化，给r,c赋值
};
//is_valid函数参数分别是：数组，起始点，之前的颜色，新颜色。
//is_valid函数判断该点是否可以改成新颜色。即在矩阵范围内，和起始点的颜色一样，并且没有更改成新颜色。
bool is_valid(char image[ROWS][COLS], Point pt,int prev_color, int new_color) {
    int r = pt.r;
    int c = pt.c;
    //这部分判断是新点的位置在边界内
    return (0 <= r && r < ROWS && 0 <= c && c < COLS &&
            image[r][c]==prev_color && image[r][c] != new_color);//空1，颜色和起始点的一样，而不是新的。
}
//flood_fill泛洪函数，参数如下：矩阵数组，起始点，新颜色。
void flood_fill(char image[ROWS][COLS], Point cur, int new_color) {
    queue<Point> queue;  //广搜，用到队列存要搜索点。元素是点的结构体
    queue.push(cur);  //把起始点cur放到队列里

    int prev_color = image[cur.r][cur.c];  //把起始点的原来颜色给到变量prev_color
    image[cur.r][cur.c]=new_color;//空2，把起始点的颜色更新为new_color

    while (!queue.empty()) { //判断队列是是否为空
        Point pt = queue.front ();  //把队列中第一个元素赋值给pt
        queue.pop ();   //队列第一个元素出列
         //开个新数组points，把pt元素的上下左右元素放进points数组
        Point points[4] = {Point(pt.r+1,pt.c), Point(pt.r - 1, pt.c),//空3，右边的点
                           Point(pt.r, pt.c + 1), Point(pt.r, pt.c - 1)};
        //将Points数组的元素挨个取出来给到p
        for (auto p : points) {
            //用is_valid函数判断，是否可以改颜色
            if (is_valid(image, p, prev_color, new_color)) {
               image[p.r][p.c]=new_color; //空4，将p点更改颜色
                queue.push(p);  //空5，将p点放到队列中
            }
        }
    }
}

int main() {
    //初始化数组
    char image[ROWS][COLS] = {{'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g'},
                              {'g', 'g', 'g', 'g', 'g', 'g', 'r', 'r'},
                              {'g', 'r', 'r', 'g', 'g', 'r', 'g', 'g'},
                              {'g', 'b', 'b', 'b', 'b', 'r', 'g', 'r'},
                              {'g', 'g', 'g', 'b', 'b', 'r', 'g', 'r'},
                              {'g', 'g', 'g', 'b', 'b', 'b', 'b', 'r'},
                              {'g', 'g', 'g', 'g', 'g', 'b', 'g', 'g'},
                              {'g', 'g', 'g', 'g', 'g', 'b', 'b', 'g'}};
    
    Point cur(4, 4);  //起始点
    char new_color = 'y';  //要更改的颜色

    flood_fill(image, cur, new_color);  //调用泛洪函数
    //输出新数组
    for (int r = 0; r < ROWS; r++) { 
        for (int c = 0; c < COLS; c++) {
            cout << image[r][c] <<' ';
        }
        cout << endl;
    }
//输出:
// g g g g g g g g
// g g g g g g r r
// g r r g g r g g
// g y y y y r g r
// g g g y y r g r
// g g g y y y y r
// g g g g g y g g
// g g g g g y y g

    return 0;
}