小埋与扫雷题解_八连通块

这里附上题目链接：小埋与扫雷。

							     		~~手动分割~~ 
1

题目

注：八连通




注：打红点的格就是
而粗红线覆盖的部分就是“空”。

名词解释

1.八连通

如图，橙色方块分别在白方块的4个对角，绿色方块则分别在白方块的上下左右。从白色格分别向8个方向出发，可到达图中的任意格。所以图示区域就是一个八连通区域。

八连通指的是从区域内每一格出发，可通过向八个方向移动（即上、下、左、右、左上、右上、左下、右下），在不越出区域的前提下，到达区域内的任意小格。

2.空

所谓的空其实就是指由扫雷地图中没有数字的格组成的连通块（从区域内每一格出发，可通过向四个方向移动（即上、下、左、右），在不越出区域的前提下，到达区域内的任意小格。）

上图橙色区域就是一个连通块。

3. 地图组成

扫雷地图里有三种格子：地雷格（此格为地雷）、数字格（此格不为地雷，但此格周围八格中有若干枚地雷）、空格（此格不为地雷，且此格周围八格中没有地雷）（即没有数字的格）。

思路解析

题目已经给出了3bv的计算公式
所以，解题分为两步：

1.计算周围八格没有“空格”的数字格数目

由

• 先将输入的地图转化一下，将地图上的格子划分为上图中的三类：用9表示地雷格，1-8表示数字格，0表示空格。

int transform_map()//先将输入的地图进行转换
{
    int i,j,y,mine_num=0;//mine_num代表每格的周围八格中地雷数
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(input_map[i][j])//若此格为地雷
            {
                trans_map[i][j]=9;//使用数字9来表示地雷格
            }
            else//若此格不为地雷
            {
                mine_num=0;//每次都要将地雷计数器清零
                //开始检查此格周围八格的地雷数
                for(y=j-1;y<=j+1;y++)//先检查(i,j)格上一行的3格
                {
                    if(boundary_determination(i-1,y))//若坐标未超出边界
                    {
                        if(input_map[i-1][y])//若此格有地雷
                        {
                            mine_num++;//则(i,j)格子的周围地雷数加一
                        }
                    }
                }
                for(y=j-1;y<=j+1;y++)//再检查(i,j)格下一行的3格
                {
                    if(boundary_determination(i+1,y))//若坐标未超出边界
                    {
                        if(input_map[i+1][y])//若此格有地雷
                        {
                            mine_num++;//则(i,j)格子的周围地雷数加一
                        }
                    }
                }
                //最后检查(i,j)格的左右两格
                if(boundary_determination(i,j-1))//若坐标未超出边界
                {
                    if(input_map[i][j-1])//若此格有地雷
                    {
                        mine_num++;
                    }
                }
                if(boundary_determination(i,j+1))//若坐标未超出边界
                {
                    if(input_map[i][j+1])//若此格有地雷
                    {
                        mine_num++;
                    }
                }
                trans_map[i][j]=mine_num;//1-8表示数字格，0表示空格
            }
        }
    }
    return 0;
}
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

• 计算周围八格没有“空格”的“数字格”的个数number_1

	//计算周围八格没有“空格”的“数字”个数number_1
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(trans_map[i][j]==0||trans_map[i][j]==9)//若此格为地雷或空格
            {
                continue;
            }
            else//若此格是数字格
            {
            	//分别检查(i,j)格周围八个格有无空格
                if(boundary_determination(i-1,j-1))
                {
                    if(!trans_map[i-1][j-1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i-1,j))
                {
                    if(!trans_map[i-1][j])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i-1,j+1))
                {
                    if(!trans_map[i-1][j+1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i,j-1))
                {
                    if(!trans_map[i][j-1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i,j+1))
                {
                    if(!trans_map[i][j+1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i+1,j-1))
                {
                    if(!trans_map[i+1][j-1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i+1,j))
                {
                    if(!trans_map[i+1][j])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i+1,j+1))
                {
                    if(!trans_map[i+1][j+1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                number_1++;//周围八格没有“空格”的“数字”个数number_1加一
            }
        }
    }
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

2.计算“空"的个数个数number_2

• 使用DFS算法在图里找连通块

int DFS(int x,int y)
{
    int j;
    if(!boundary_determination(x,y))//若坐标越界
    {
        return 0;
    }
    if(trans_map[x][y])//若该格不为空格
    {
        return 0;
    }
    if(visit[x][y])//若该空格已访问过
    {
        return 0;
    }
    visit[x][y]=1;//将该空格标记为已访问
    //接下来分别向8个方向尝试访问
    for(j=y-1;j<=y+1;j++)
    {
        DFS(x-1,j);
    }
    for(j=y-1;j<=y+1;j++)
    {
        DFS(x+1,j);
    }
    DFS(x,y-1);
    DFS(x,y+1);
    return 1;
}

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

• 计数

    //再计算“空"的个数个数number_2
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(DFS(i,j))//若找到一个连通块
            {
                number_2++;//计数器加一
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11

AC代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n,m;//地图有n行m列
int number_1,number_2;
int visit[1000][1000];//数组visit用于记忆地图某一格是否被访问过
int input_map[1000][1000],trans_map[1000][1000];//input_map存储输入的地图,trans_map存储转换后的地图

int boundary_determination(int x,int y)
{
    if(x<0||x>=n||y<0||y>=m)//若坐标超出边界
    {
        return 0;//返回假值
    }
    return 1;//返回真值
}

int transform_map()//先将输入的地图进行转换
{
    int i,j,y,mine_num=0;//mine_num代表每格的周围八格中地雷数
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(input_map[i][j])//若此格为地雷
            {
                trans_map[i][j]=9;//使用数字9来表示地雷格
            }
            else//若此格不为地雷
            {
                mine_num=0;
                //开始检查此格周围八格的地雷数
                for(y=j-1;y<=j+1;y++)//先检查(i,j)格上一行的
                {
                    if(boundary_determination(i-1,y))//若未超出边界
                    {
                        if(input_map[i-1][y])//若此格有地雷
                        {
                            mine_num++;//则(i,j)格子的周围地雷数加一
                        }
                    }
                }
                for(y=j-1;y<=j+1;y++)//再检查(i,j)格下一行的
                {
                    if(boundary_determination(i+1,y))//若未超出边界
                    {
                        if(input_map[i+1][y])//若此格有地雷
                        {
                            mine_num++;//则(i,j)格子的周围地雷数加一
                        }
                    }
                }
                //最后检查剩余两格
                if(boundary_determination(i,j-1))
                {
                    if(input_map[i][j-1])
                    {
                        mine_num++;
                    }
                }
                if(boundary_determination(i,j+1))
                {
                    if(input_map[i][j+1])
                    {
                        mine_num++;
                    }
                }
                trans_map[i][j]=mine_num;
            }
        }
    }
    return 0;
}

int DFS(int x,int y)
{
    int j;
    if(!boundary_determination(x,y))//若坐标越界
    {
        return 0;
    }
    if(trans_map[x][y])//若该格不为空格
    {
        return 0;
    }
    if(visit[x][y])//若该空格已访问过
    {
        return 0;
    }
    visit[x][y]=1;//将该空格标记为已访问
    //接下来分别向8个方向尝试访问
    for(j=y-1;j<=y+1;j++)
    {
        DFS(x-1,j);
    }
    for(j=y-1;j<=y+1;j++)
    {
        DFS(x+1,j);
    }
    DFS(x,y-1);
    DFS(x,y+1);
    return 1;
}

int main()
{
    int i,j;
    //输入数据
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            scanf("%d",&input_map[i][j]);
        }
    }
    //先转换地图
    transform_map();
    //计算周围八格没有“空格”的“数字”个数number_1
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(trans_map[i][j]==0||trans_map[i][j]==9)//若此格为地雷或空格
            {
                continue;
            }
            else//若此格既不为地雷也不是空格
            {
            	//分别检查(i,j)格周围八个格
                if(boundary_determination(i-1,j-1))
                {
                    if(!trans_map[i-1][j-1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i-1,j))
                {
                    if(!trans_map[i-1][j])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i-1,j+1))
                {
                    if(!trans_map[i-1][j+1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i,j-1))
                {
                    if(!trans_map[i][j-1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i,j+1))
                {
                    if(!trans_map[i][j+1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i+1,j-1))
                {
                    if(!trans_map[i+1][j-1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i+1,j))
                {
                    if(!trans_map[i+1][j])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                if(boundary_determination(i+1,j+1))
                {
                    if(!trans_map[i+1][j+1])//若此格为空格
                    {
                        continue;//则直接进入下一循环
                    }
                }
                number_1++;//周围八格没有“空格”的“数字”个数number_1加一
            }
        }
    }
    //再计算“空"的个数个数number_2
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(DFS(i,j))
            {
                number_2++;
            }
        }
    }
    //输出结果
    printf("%d",number_1+number_2);
    return 0;
}
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206