【FLOOD FILL专题】【蓝桥杯备考训练】：扫雷、动态网格、走迷宫、画图、山峰和山谷【已更新完成】

1、扫雷（Google Kickstart2014 Round C Problem A）

2、动态网格（Google Kickstart2015 Round D Problem A）

3、走迷宫（模板）

4、画图（第六次CCF计算机软件能力认证）

5、山峰和山谷（POI2007 & 《信息学奥赛一本通》）

1、扫雷（Google Kickstart2014 Round C Problem A）

扫雷是一种计算机游戏，在 20 世纪 80 年代开始流行，并且仍然包含在某些版本的 Microsoft Windows 操作系统中。

在这个问题中，你正在一个矩形网格上玩扫雷游戏。

最初网格内的所有单元格都呈未打开状态。

其中 M 个不同的单元格中隐藏着 M 个地雷。

其他单元格内不包含地雷。

你可以单击任何单元格将其打开。

如果你点击到的单元格中包含一个地雷，那么游戏就会判定失败。

如果你点击到的单元格内不含地雷，则单元格内将显示一个 0 到 8 之间的数字（包括 0 和 8），这对应于该单元格的所有相邻单元格中包含地雷的单元格的数量。

如果两个单元格共享一个角或边，则它们是相邻单元格。

另外，如果某个单元格被打开时显示数字 0，那么它的所有相邻单元格也会以递归方式自动打开。

当所有不含地雷的单元格都被打开时，游戏就会判定胜利。

例如，网格的初始状态可能如下所示（* 表示地雷，而 c 表示第一个点击的单元格）：

*..*...**.
....*.....
..c..*....
........*.
..........

被点击的单元格旁边没有地雷，因此当它被打开时显示数字 00，并且它的 88 个相邻单元也被自动打开，此过程不断继续，最终状态如下：

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

此时，仍有不包含地雷的单元格（用 . 字符表示）未被打开，因此玩家必须继续点击未打开的单元格，使游戏继续进行。

你想尽快赢得游戏胜利并希望找到赢得游戏的最低点击次数。

给定网格的尺寸（N×N），输出能够获胜的最小点击次数。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N，表示游戏网格的尺寸大小。

接下来 N 行，每行包含一个长度为 N 的字符串，字符串由 .（无雷）和 *（有雷）构成，表示游戏网格的初始状态。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x 是组别编号（从 1 开始），y 是获胜所需的最小点击次数。

数据范围

1≤T≤100
1≤N≤300

输入样例：

2
3
..*
..*
**.
5
..*..
..*..
.*..*
.*...
.*...

输出样例：

Case #1: 2
Case #2: 8

思路：

预处出每个点的数字再对0的位置进行搜索，最后对漏网之鱼进行处理

代码：

#include<bits/stdc++.h>
using namespace std;
const int N =310;
int dx[8]={1,1,1,0,0,-1,-1,-1},dy[8]={1,0,-1,1,-1,1,0,-1};
int num[N][N],st[N][N];
char g[N][N];    //记录扫雷整张地图
void bfs(int a,int b,int n)   //寻找0点周围的所有点，标记为已遍历
{st[a][b]=1;num[a][b]=-1;for(int i=0;i<8;i++){int x=a+dx[i],y=b+dy[i];if(x>=0 && x<n && y>=0 && y<n){if(!st[x][y] && num[x][y]!=-1){if(num[x][y]>0) st[x][y]=1,num[x][y]=-1;if(num[x][y]==0) bfs(x,y,n);}}}
}
int main()
{int T,n;scanf("%d",&T);for(int t=1;t<=T;t++){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%s",g[i]);memset(num,0,sizeof num);for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(g[i][j]!='*')    //不是雷的要统计8个点上雷的总个数{for(int k=0;k<8;k++){int x=i+dx[k],y=j+dy[k];if(x>=0 && x<n && y>=0 && y<n && g[x][y]=='*'){num[i][j]++;}}}else num[i][j]=-1;   //如果是雷则标记为-1}}memset(st,0,sizeof st);int ans=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(num[i][j]==0 && !st[i][j])     //找到一个0点ans++，同时进行bfs{ans++;  bfs(i,j,n);}}}for(int i=0;i<n;i++){for(int j=0;j<n;j++)if(num[i][j]!=-1 && !st[i][j]) ans++;  //找到漏网之鱼，每找到一个就ans++}printf("Case #%d: %d\n",t,ans);}return 0;
}

2、动态网格（Google Kickstart2015 Round D Problem A）

我们有一个 R 行 C 列的矩形网格，其中每个方格内的数字都是 0 或 1。

我们将在网格上执行 N 个操作，每个操作都是以下之一：

操作 M：将网格的一个单元格中的数字更改为 0 或 1。
操作 Q：确定 1 的不同连通区域的数量。 1 的连通区域是指矩阵内全部为 1 的连通的单元格的子集，在子集区域内通过沿着共享边缘在单元格之间行进，可以从该区域中的任何单元格到达该区域中的任何其他单元格。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含两个整数 R 和 C，表示矩形网格的行数和列数。

接下来 R 行，每行包含一个长度为 C 的由 1 和 0 构成的字符串，表示矩阵网格的初始状态。

接下来一行，包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令共两种，如下所示：

M x y z，表示 M 指令，具体含义为将第 x 行第 y 列的方格内的值变为 z。
Q，表示 Q 指令，表示进行一次询问。

输出格式

对于每组测试数据，第一行输出 Case #x:，其中 x 为组别编号（从 1 开始）。

接下来 Q 行，每行输出一个询问的结果。

数据范围

1≤T≤10
1≤R,C≤100
0≤x<R
0≤y<C
0≤z≤1
1≤N≤1000

输入样例：

输出样例：

Case #1:
4
2
2
2

思路：

比较简单的连通块的统计，只是加上了些许操作而已

代码：

#include<bits/stdc++.h>using namespace std;const int N=1001;int g[N][N];
int st[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};int t;
int n,m;
int q;void bfs(int x,int y)
{st[x][y]=1;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx>=0 && ny>=0 && nx<n && ny<m && !st[nx][ny] && g[nx][ny]==1){bfs(nx,ny);}}}int main()
{cin>>t;int cnt=1;while(t--){cin>>n>>m;for(int i=0;i<n;i++){string s;cin>>s;//cout<<s<<endl;for(int j=0;j<m;j++){			g[i][j]=s[j]-'0';//cout<<s;}}/*for(int i=0;i<n;i++){for(int j=0;j<m;j++){			cout<<g[i][j];}cout<<endl;}*///cout<<"read";cin>>q;cout<<"Case #"<<cnt<<":"<<endl;cnt++;while(q--){char op;cin>>op;if(op=='Q'){//printf("Case #%d:",&cnt);memset(st,0,sizeof st);int res=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(g[i][j]==1 && !st[i][j]){//cout<<"ko"<<endl;bfs(i,j);res++;}}cout<<res<<endl;}else{int x,y,v;cin>>x>>y>>v;g[x][y]=v;}}}return 0;
}

3、走迷宫（模板）

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m)处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m)处的数字为 0，且一定至少存在一条通路。

输入格式

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

输入样例：

输出样例：

思路：

深搜加距离记录（距离数组d同时作为st数组用）一遍过

代码：

#include<bits/stdc++.h>using namespace std;const int N=101;typedef pair<int,int> PII;int n,m;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int g[N][N];
int d[N][N];
int hh,tt;
PII q[N*N];int bfs()
{q[tt]={0,0};d[0][0]=0;while(hh<=tt){auto t=q[hh++];int x=t.first;int y=t.second;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx>=0 && nx<n && ny>=0 && ny<m && d[nx][ny]==-1 &&g[nx][ny]==0){d[nx][ny]=d[x][y]+1;//cout<<d[nx][ny]<<endl;q[++tt]={nx,ny};}}}return d[n-1][m-1];}int main()
{cin>>n>>m;memset(d,-1,sizeof d);for(int i=0;i<n;i++)for(int j=0;j<m;j++){scanf("%d",&g[i][j]);}cout<<bfs();return 0;
}

4、画图（第六次CCF计算机软件能力认证）

用 ASCII 字符来画图是一件有趣的事情，并形成了一门被称为 ASCII Art 的艺术。

例如，下图是用 ASCII 字符画出来的 CSPRO 字样。

　　..____.____..____..____...___.../.___/.___||.._.\|.._.\./._.\.|.|...\___.\|.|_).|.|_).|.|.|.||.|___.___).|..__/|.._.<|.|_|.|.\____|____/|_|...|_|.\_\\___/.

本题要求编程实现一个用 ASCII 字符来画图的程序，支持以下两种操作：

画线：给出两个端点的坐标，画一条连接这两个端点的线段。简便起见题目保证要画的每条线段都是水平或者竖直的。水平线段用字符 - 来画，竖直线段用字符 | 来画。如果一条水平线段和一条竖直线段在某个位置相交，则相交位置用字符 + 代替。
填充：给出填充的起始位置坐标和需要填充的字符，从起始位置开始，用该字符填充相邻位置，直到遇到画布边缘或已经画好的线段。注意这里的相邻位置只需要考虑上下左右 4 个方向，如下图所示，字符 @ 只和 4 个字符 * 相邻。

　　.*.*@*.*.

输入格式

第 1 行有三个整数 m,n 和 q。m 和 n分别表示画布的宽度和高度，以字符为单位。q 表示画图操作的个数。

第 2 行至第 q+1 行，每行是以下两种形式之一：

0 x1 y1 x2 y2：表示画线段的操作，(x1,y1)和 (x2,y2)分别是线段的两端，满足要么 x1=x2 且 y1≠y2，要么 y1=y2 且 x1≠x2。
1 x y c：表示填充操作，(x,y) 是起始位置，保证不会落在任何已有的线段上；c 为填充字符，是大小写字母。

画布的左下角是坐标为 (0,0) 的位置，向右为 x 坐标增大的方向，向上为 y 坐标增大的方向。

这 q 个操作按照数据给出的顺序依次执行。画布最初时所有位置都是字符 .（小数点）。

输出格式

输出有 n 行，每行 m 个字符，表示依次执行这 q 个操作后得到的画图结果。

数据范围

2≤m,n≤100
0≤q≤100，
0≤x<m（x 表示输入数据中所有位置的 x 坐标），
0≤y<n（y 表示输入数据中所有位置的 y 坐标）。

输入样例1：

输出样例1：

AAAA
A--A

输入样例2：

16 13 9
0 3 1 12 1
0 12 1 12 3
0 12 3 6 3
0 6 3 6 9
0 6 9 12 9
0 12 9 12 11
0 12 11 3 11
0 3 11 3 1
1 4 2 C

输出样例2：

................
...+--------+...
...|CCCCCCCC|...
...|CC+-----+...
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC+-----+...
...|CCCCCCCC|...
...+--------+...
................

思路：

我们选择反着读入行列的信息，这样就可以把起点定义为我们熟悉的左上角

洪水覆盖法在这里体现在对封闭图形的填充

代码：

//注意这里的输入是先输入的是列，然后是行
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m ,q;char g[N][N];
bool st[N][N];void change(int x1, int y1, int x2, int y2){if(x1 == x2){// 同一行for(int i = y1; i <= y2; i ++){if( g[x1][i] == '|'|| g[x1][i] == '+') g[x1][i]= '+';else g[x1][i] = '-';}}// 同一列else if ( y1 == y2){for(int i = x1; i <= x2; i ++){if( g[i][y1] == '-' || g[i][y1] == '+') g[i][y1] = '+';else g[i][y1] = '|';}}
}void paint(int x, int y, char s){st[x][y] = true;g[x][y] = s;int dx[4] = { -1, 0, 1, 0}, dy[4] = { 0, 1, 0, -1};for(int i = 0; i < 4; i ++){int a = x + dx[i], b = y + dy[i];if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]) continue;if(g[a][b] == '|' || g[a][b] == '-' || g[a][b] == '+') continue;paint(a, b, s);}
}
int main(){cin >> m >> n >> q;for(int i = 0; i < n; i ++)for(int j = 0; j < m; j ++)g[i][j] = '.';while(q --){int op;cin >> op;if(op == 0){// x和y反着读入int x1, y1, x2, y2;cin >> y1 >> x1 >> y2 >> x2;if(x1 > x2) swap(x1, x2);if(y1 > y2) swap(y1, y2);change(x1, y1, x2, y2);}else{int x, y;char s;// x和y反着读入cin >> y >> x >> s;memset(st, 0, sizeof st);paint(x, y, s);}}for(int i = n -1; i >= 0; i--){for(int j = 0; j < m; j++)cout << g[i][j];cout << endl;}
}

5、山峰和山谷（POI2007 & 《信息学奥赛一本通》）

FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。

为了能够对旅程有一个安排，他想知道山峰和山谷的数量。

给定一个地图，为FGD想要旅行的区域，地图被分为 n×n 的网格，每个格子 (i,j) 的高度 w(i,j)是给定的。

若两个格子有公共顶点，那么它们就是相邻的格子，如与 (i,j)相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)。

我们定义一个格子的集合 S 为山峰（山谷）当且仅当：

S 的所有格子都有相同的高度。
S 的所有格子都连通。
对于 s 属于 S，与 s 相邻的 s' 不属于 S，都有 ws>ws'（山峰），或者 ws<ws'（山谷）。
如果周围不存在相邻区域，则同时将其视为山峰和山谷。

你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

输入格式

第一行包含一个正整数 n，表示地图的大小。

接下来一个 n×n 的矩阵，表示地图上每个格子的高度 w。

输出格式

共一行，包含两个整数，表示山峰和山谷的数量。

数据范围

1≤n≤1000
0≤w≤109

输入样例1：

输出样例1：

2 1

输入样例2：

输出样例2：

3 3

样例解释

样例1：

样例2：

思路：

加两个参数表示有无山峰或者山谷即可，遇到相同的数字就继续bfs，记得bool参数加引用，不然不会改变原来的变量

dfs代码（超出内存版）：

bfs（爆栈）

//dfs超出内存了 
#include<bits/stdc++.h>using namespace std; const int N=1000;int g[N][N];int st[N][N];int dx[]={-1,1,0,0,1,1,-1,-1};
int dy[]={0,0,-1,1,1,-1,-1,1};//八个方向（新增左上左下右上右下）
int n;void dfs(int x,int y,bool &h,bool &l)//这里必须引用！
{st[x][y]=1;for(int i=0;i<8;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx>=0 && ny>=0 && nx<n && ny<n){if(g[nx][ny]<g[x][y])l=true;//有比他更低的else if(g[nx][ny]>g[x][y])h=true;//有比他更高的else if(g[nx][ny]==g[x][y]  && !st[nx][ny]){dfs(nx,ny,h,l);}}}}int main()
{cin>>n;int peak=0,valley=0;for(int i=0;i<n;i++)for(int j=0;j<n;j++){scanf("%d",&g[i][j]);	}	for(int i=0;i<n;i++)for(int j=0;j<n;j++){if(!st[i][j]){bool h=false;bool l=false;dfs(i,j,h,l);if(!h)peak++;//cout<<i<<""<<j<<endl;if(!l)valley++;//cout<<i<<""<<j<<endl;}}cout<<peak<<" "<<valley;return 0;
}

bfs代码（AC成功）：

#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N = 1010;
int n;
int h[N][N];
bool st[N][N];
void bfs (int sx,int sy,bool &has_higher,bool &has_lower) {queue <PII> q;q.push ({sx,sy});while (!q.empty ()) {PII t = q.front ();q.pop ();for (int i = t.x - 1;i <= t.x + 1;i++) {for (int j = t.y - 1;j <= t.y + 1;j++) {if (i < 1 || i > n || j < 1 || j > n) continue;if (h[i][j] != h[t.x][t.y]) {if (h[i][j] > h[t.x][t.y]) has_higher = true;else has_lower = true;}else if (!st[i][j]) {q.push ({i,j});st[i][j] = true;}}}}
}
int main () {cin >> n;for (int i = 1;i <= n;i++) {for (int j = 1;j <= n;j++) cin >> h[i][j];}int peak = 0,valley = 0;for (int i = 1;i <= n;i++) {for (int j = 1;j <= n;j++) {if (!st[i][j]) {bool has_higher = false,has_lower = false;bfs (i,j,has_higher,has_lower);if (!has_higher) peak++;if (!has_lower) valley++;}}}cout << peak << ' ' << valley << endl;return 0;
}

dfs代码（AC成功版):

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1010;int n;
bool f[N][N];
int h[N][N];
//　将两个需要返回的参数，设置为全局变量，则可以正常通过此题。
//  将两个需要返回的参数，设置为带地址符的变量，则MLE
bool has_higher, has_lower;
//  657 ms
void dfs(int sx, int sy) {f[sx][sy] = true;for (int x = sx - 1; x <= sx + 1; x++) {for (int y = sy - 1; y <= sy + 1; y++) {if (x < 0 || x >= n || y < 0 || y >= n) continue;if (h[sx][sy] != h[x][y]) { //高度不相等if (h[sx][sy] < h[x][y]) has_higher = true;if (h[sx][sy] > h[x][y]) has_lower = true;} else { //高度相等if (f[x][y]) continue;dfs(x, y);}}}
}
int vally, peak;
int main() {//加快读入cin.tie(0), ios::sync_with_stdio(false);cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> h[i][j];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (!f[i][j]) {has_higher = has_lower = false;dfs(i, j);if (has_higher && has_lower) continue;if (has_higher) vally++;if (has_lower) peak++;}}}//对于不存在山峰+山谷的一马平地，山峰山谷都输出1if (peak == 0 && vally == 0) peak = 1, vally = 1;printf("%d %d\n", peak, vally);return 0;
}