PDF文档公众号回复关键字:20240620
2022 CSP-J 阅读程序2
完善程序 (单选题 ，每小题3分，共30分)
2 (洪水填充) 现有用字符标记像素颜色的8 * 8图像。颜色填充操作描述如下：给定起始像素的位置和待填充的颜色，将起始像素和所有可达像素(可达的定义：经过一次或多次的向上、下、左、右四个方向移动所能到达且终点和路径上所有像素的颜色都与起始像素颜色相同)，替换为给定的颜色
试补全模拟程序
01 #include<bits/stdc++.h>
02 using namespace std;
03
04 const int ROWS = 8;
05 const int COLS = 8;
06
07 struct Point{
08 int r,c;
09 Point(int r,int c):r(r),c(c){}
10 };
11
12 bool is_valid(char image[ROWS][COLS],Point pt,
13 int prev_color,int new_color){
14 int r=pt.r;
15 int c=pt.c;
16 return (0<=r&&r<ROWS&&0<=c && c<COLS &&
17 --1-- && image[r][c]!=new_colr);
18 }
19
20 void flood_fill(char image[ROWS][COLS],Point cur,int new_color){
21 queue<Point> queue;
22 queue.push(cur);
23
24 int prev_color=image[cur.r][cur.c];
25 --2--;
26
27 while(!queue.empty()){
28 Point pt=queue.front();
29 queue.pop();
30
31 Point point[4]={--3--,Point(pt.r-1,pt.c),
32 Point(pt.r,pt.c+1),Point(pt.r,pt.c-1)}
33 for(auto p:points){
34 if(is_valid(image,p,prev_color,new_color)){
35 --4--;
36 --5--;
37 }
38 }
39 }
40 }
41
42 int main(){
43 char image[ROW][COLS]={{'g','g','g','g','g','g','g','g'},
44 {'g','g','g','g','g','g','r','r'},
45 {'g','r','r','g','g','r','g','g'},
46 {'g','b','b','b','b','r','g','r'},
47 {'g','g','g','b','b','r','g','r'},
48 {'g','g','g','b','b','b','b','r'},
49 {'g','g','g','g','g','b','g','g'},
50 {'g','g','g','g','g','b','b','g'}};
51
52 Point cur(4,4);
53 char new_color ='y';
54
55 flood_fill(image,cur,new_color);
56
57 for(int r=0;r<ROWS;r++){
58 for(int c=0;c<COLS;c++){
59 cout<<image[r][c]<<" ";
60 }
61 cout<<endl;
62 }
63 // 输出
64 // g g g g g g g g
65 // g g g g g g r r
66 // g r r g g r g g
67 // g y y y y r g r
68 // g g g y y r g r
69 // g g g y y y y r
70 // g g g g g y g g
71 // g g g g g y y g
72
73 return 0;
74 }
40.①处应填( )
A. image[r] [c] == prew_color
B. image[r] [c] != prew_color
C. image[r] [c] == new_color
D. image[r] [c] != new_color
41.②处应该填( )
A. image[cur.r+1] [cur.c] == new_color
B. image[cur.r] [cur.c] == new_color
C. image[cur.r] [cur.c+1] == new_color
D. image[cur.r] [cur.c] == prew_color
42.③处应该填( )
A. Point(pt.r,pt.c)
B. Point(pt.r,pt.c+1)
C. Point(pt.r+1,pt.c)
D. Point(pt.r+1,pt.c+1)
43.④处应该填( )
A. Prew_color = image[p.r] [p.c]
B. new_color = image[p.r] [p.c]
C. image[p.r] [p.c]=prev_color
D. image[p.r] [p.c] =new_color
44.⑤处应该填( )
A. queue.push§;
B. queue.push(pt)
C. queue.push(cur)
D. queue.push(Point(ROWS,COLS))
2 相关知识点
1) 结构体构造方法
//1 不指定构造函数
#include<bits/stdc++.h>
using namespace std;
/*
定义结构体 包括2个成员x和y
*/
struct xy{
int x;
int y;
};
int main(){
xy xy1;//声明结构体变量xy1
xy1.x=1;//对成员变量x赋值
xy1.y=2;//对成员变量y赋值
cout<<xy1.x<<" "<<xy1.y;//输出成员变量x和y
return 0;
}
//2 结构体赋值构造函数
#include<bits/stdc++.h>
using namespace std;
/*
结构体构造函数体内为成员变量赋值
*/
struct xy{
int x;
int y;
//和结构体名称相同的函数称为构造函数
xy(int _x,int _y){//通过构造函数对成员变量赋值
x=_x;
y=_y;
}
};
int main(){
xy xy1=xy(1,2);//通过构造函数传入参数给成员变量x,y
cout<<xy1.x<<" "<<xy1.y;//输出成员变量x和y
return 0;
}
// 3 初始化列表初始化成员的构造函数
#include<bits/stdc++.h>
using namespace std;
/*
C++提供了给成员变量初始化并赋值的方式，这就是初始化列表。
在构造函数的()后，{}之前写，格式是冒号+成员名（初始值），
对与自定义类型则是调用它的构造函数初始化
*/
struct xy{
int x;
int y;
xy(int x,int y):x(x),y(y){}//初始化列表方式对成员变量进行初始化
};
int main(){
xy xy1=xy(1,2);//通过构造函数传入参数给成员变量x,y
cout<<xy1.x<<" "<<xy1.y;//输出成员变量x和y
return 0;
}
2) 子图
设G = <V,E>, G’ = <V’,E’>为两个图（同为无向图或同为有向图），若V’∈ V 且 E’∈E，则称G’是G的子图，G是G’的母图
3) 极大连通子图
对于图的某一子图，它包含了图中尽可能多的顶点以及尽可能多的边，以至于它再加上一个点或者边之后它就不连通了，此时这个图就是极大连通子图
4) 连通分量
无向图G的极大连通子图称为G的连通分量
5) 连通块
连通块（Connected Components），也称为连通分量，是图论中的一个概念
6) 洪水填充 flood fill
洪水填充是CSP-J需要掌握的一个知识点
具体过程从一个起始节点开始，把附近与其连通的节点提取出或填充成不同颜色颜色，直到封闭区域内的所有节点都被处理过为止
洪水填充主要是找有多少个连通块及每个连通块的大小等
7) auto 关键字
C++11引入了auto类型说明符，它允许在声明变量的时候根据变量初始化表达式的类型自动为变量选择匹配的类型。
通过使用auto，我们不需要手动指定变量的类型，而是让编译器来为我们推断变量的类型
#include<bits/stdc++.h>
using namespace std;
/*
它允许在声明变量的时候根据变量初始化表达式的类型自动为变量选择匹配的类型。
通过使用auto，我们不需要手动指定变量的类型，而是让编译器来为我们推断变量的类型
*/
int main(){
auto x = 42;//自动变成匹配的int
cout<<"x的值为:"<<x<<endl;
float a=10.1;
auto y=a;//自动变成匹配的float
cout<<"y的值为:"<<y<<endl;
return 0;
}
自动推断出结构体类型示例
#include<bits/stdc++.h>
using namespace std;
/*
自动推断出结构体类型
*/
struct xy{
int x,y;
xy(int x,int y):x(x),y(y){}
};
int main(){
xy list[4]={xy(1,2),xy(3,4),xy(5,6),xy(7,8)};
for(auto t:list){
cout<<t.x<<" "<<t.y<<endl;
}
return 0;
}
上面代码需要在C++11编译器运行，DEV-C++设置方法如下
工具–编译器选项进入
进入编译器选项进行设置
设置好语言标准为C++11后，重新编译即可
3 思路分析
40.①处应填( )
A. image[r] [c] == prew_color
B. image[r] [c] != prew_color
C. image[r] [c] == new_color
D. image[r] [c] != new_color
分析
/*
此方法判断是否可以继续填充，继续填充遵循3个规则
不越界，颜色相同，不重复走
0<=r&&r<ROWS&&0<=c && c<COLS -- 不越界
image[r][c]!=new_colr --不是新颜色才走，表示不重复走
缺少颜色相同，必须和之前颜色相同时才填充
所以判断当前格是否和之前颜色相同 image[r] [c] == prew_color
*/
12 bool is_valid(char image[ROWS][COLS],Point pt,
13 int prev_color,int new_color){
14 int r=pt.r;
15 int c=pt.c;
16 return (0<=r&&r<ROWS&&0<=c && c<COLS &&
17 --1-- && image[r][c]!=new_colr);
18 }
41.②处应该填( B )
A. image[cur.r+1] [cur.c] = new_color
B. image[cur.r] [cur.c] = new_color
C. image[cur.r] [cur.c+1] = new_color
D. image[cur.r] [cur.c] = prew_color
分析
/*
填充起点，起点也需要涂成新颜色
所以把新颜色new_color赋值给image[cur.r] [cur.c]
*/
24 int prev_color=image[cur.r][cur.c];
25 --2--;
42.③处应该填( C )
A. Point(pt.r,pt.c)
B. Point(pt.r,pt.c+1)
C. Point(pt.r+1,pt.c)
D. Point(pt.r+1,pt.c+1)
分析
/*
需要向 向上、下、左、右四个方向填充
如下point数组往4个方向拓展
Point(pt.r-1,pt.c) --向上
Point(pt.r,pt.c+1) --向右
Point(pt.r,pt.c-1) --向左
还缺少向下r+1
所以是 Point(pt.r+1,pt.c)
*/
31 Point point[4]={--3--,Point(pt.r-1,pt.c),
32 Point(pt.r,pt.c+1),Point(pt.r,pt.c-1)}
43.④处应该填( )
A. Prew_color = image[p.r] [p.c]
B. new_color = image[p.r] [p.c]
C. image[p.r] [p.c]=prev_color
D. image[p.r] [p.c] =new_color
分析
/*
如果拓展的这个格子p，不出界，颜色相同，没填充过
则把这个格子用新颜色填充- image[p.r] [p.c] =new_color
放入队列，下次从队列中取出继续拓展 queue.push(p);
*/
33 for(auto p:points){
34 if(is_valid(image,p,prev_color,new_color)){
35 --4--;
36 --5--;
37 }
38 }
44.⑤处应该填( A )
A. queue.push§;
B. queue.push(pt)
C. queue.push(cur)
D. queue.push(Point(ROWS,COLS))
分析
参考43题
![[leetcode hot 150]第十五题，三数之和](https://img-blog.csdnimg.cn/direct/cb45550577ee47baa1b796fc6063d0d9.png)
