二值图像是指在图像中，灰度等级只有两种，也就是说，图像中的任何像素点的灰度值均为0或者255，分别代表黑色和白色。现在给出一个 m*n的二值图像矩阵，求其中最大的白色连通块。连通按四连通计算，即上下左右相连为连通。
首先输入两个正整数m和n，保证 1<m,n<100。接下来m行，每行输入n个数，0 表示格子为黑色像素块，255表示白色像素块。保证至少有一个255的白色像素块，保证不会出现其他整数。最后输出一个整数，表示白色像素块的最大连通数量。
01
二值图像的最大连通块
01 #include
<stdio.h>
02 int main()

03 {

04 int image[
100
][
100
] = { 0 };

05 int i, j, m, n, count, max=0;

06 int front, rear;

07 int q1[100], q2[100];

08 bool visited[
100
][
100
] = ① ;

09 int dx[4] = { 0,1,0,-1 };

10 int dy[4] = { 1,0,-1,0 };

11 scanf("%d%d", &m, &n);

12 for (i = 0; i
<
m
;
i
++)

13for
 (
j
 =
0;j
 <
n
;
j
++)

14scanf
("%
d
", &
image
[
i
][
j
]);

15for
 (
i
 =
0;i
 <
m
;
i
++)

16for
 (
j
 =
0;j
 <
n
;
j
++)

17
        {

18if
 (
image
[
i
][
j
] && !
visited
[
i
][
j
])

19
            {

20
                   ② ;

21count
 =
0;
22q1
[
rear
] =
i;
23q2
[
rear
] =
j;
24visited
[
i
][
j
] =
true;
25rear
++;

26while
 ( ③ )

27
                {

28intx
 =
q1[front];
29inty
 =
q2[front];
30
                       ④ ；

31count
++;

32for
 (
intk
 =
0;k
 <=
3;k
++)

33
                    {

34intnx
 =
x
 +
dx
[
k
] ,
ny
 =
y
 +
dy
[
k
];

35if
 ((
nx
 <
0
 ||
nx
 >
= m || ny
< 0 || ny >
= n)

36 continue;

37 if( ⑤ )

38 continue;

39 q1[rear] = nx;

40 q2[rear] = ny;

41 visited[
nx
][
ny
] = true;

42 rear++;

43 }

44 if (count > max) max = count;

45 }

46 }

47 }

48 printf("%d", max);

49 }

1） ①处应填（  ）
A.{false}
B.{true}
C.true
D.false
2） ②处应填（  ）
A.front=0,rear=1
B.front=1, rear=0
C.front = rear = 0
D.front=rear=1
3） ③处应填（  ）
A.Front
B.!front
C.front != rear
D.front==rear
4）  ④处应填（  ）
A.rear++
B.front++
C.front=0
D.rear=0
5） ⑤处应填（  ）
A. !visited[nx][ny]  &&  image[nx][ny]                       
B. !visited[nx][ny]  ||  image[nx][ny]                           
C. visited[nx][ny]  &&  !image[nx][ny]                              
D. visited[nx][ny]  ||  !image[nx][ny]
【分析】
在一个m*n的矩阵中找出最大的全为255的连通块，可以对矩阵的每一个单位进行判断，首先找到第一个符合题目要求的格子，再对这个格子的上下左右进行查找，若有另一个符合要求的格子，就对这个格子进行判断。采用队列思想，先按需求建立空队列（本题建立的队列为q1和q2），再判断格子是否符合题目的要求，若符合则入队、出队、计数，每找到一个新的符合要求的格子，就把这个格子的坐标记录下来，入队、出队、计数。程序中的dx[4]和dy[4]里的数据分别代表格子向右、向下、向左、向上时坐标增减的情况，再利用四次循环就可以找到单位周围的四个位置。
填空题1解析：
当前矩阵中的所有格子都未被访问过，赋初值false。
参考答案：A
填空题2解析：
当前队列为空队列，队首和队尾都指向队首即q1[0],q2[0]。
参考答案：C
填空题3解析：
若队列不为空队列，即有符合要求的格子，则执行while，对队列中的格子进行判断；若队列不为空队列，即没有符合要求的格子，就不执行while。要判断队列是否为空队列就是要判断队首是否等于队尾，即front是否等于rear。 
参考答案：C
填空题4解析：
每出队一次，当前队列的队首就往后移一位。
参考答案：B
填空题5解析：
上下左右四个方向搜索时，若这个格子是黑色并且未被访问过就继续入队。
参考答案：D
02
参考书籍
《CCF CSP第一轮认证一本通》
ISBN：978-7-302-58146-8
作者：丁向民
定价：79元
undefined
03
精彩推荐
继续阅读
阅读原文