蓝桥杯C++大学B组一个月冲刺记录2024/3/19

蓝桥杯C++大学B组一个月冲刺记录2024/3/19

规则：每日三题

今日是打麻将输钱的一天…

1.扫雷

扫雷是一种计算机游戏，在 20 世纪 80 年代开始流行，并且仍然包含在某些版本的 Microsoft Windows 操作系统中。 在这个问题中，你正在一个矩形网格上玩扫雷游戏。 最初网格内的所有单元格都呈未打开状态。 其中 M个不同的单元格中隐藏着 M个地雷。 其他单元格内不包含地雷。 你可以单击任何单元格将其打开。 如果你点击到的单元格中包含一个地雷，那么游戏就会判定失败。 如果你点击到的单元格内不含地雷，则单元格内将显示一个 0到 8之间的数字（包括 0 和 8 ），这对应于该单元格的所有相邻单元格中包含地雷的单元格的数量。 如果两个单元格共享一个角或边，则它们是相邻单元格。 另外，如果某个单元格被打开时显示数字 0 ，那么它的所有相邻单元格也会以递归方式自动打开。 当所有不含地雷的单元格都被打开时，游戏就会判定胜利。 例如，网格的初始状态可能如下所示（* 表示地雷，而 c 表示第一个点击的单元格）： ……. …… …c…… …*. … 被点击的单元格旁边没有地雷，因此当它被打开时显示数字 0，并且它的 8个相邻单元也被自动打开，此过程不断继续，最终状态如下： ……. 1112*… 00012*… 00001111*. 00000001… 此时，仍有不包含地雷的单元格（用 . 字符表示）未被打开，因此玩家必须继续点击未打开的单元格，使游戏继续进行。 你想尽快赢得游戏胜利并希望找到赢得游戏的最低点击次数。 给定网格的尺寸（N×N），输出能够获胜的最小点击次数。

bfs + 染色法 转移条件：当该点八个方向的都不存在地雷的时候,需要bfs遍历这个点

#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int N = 305; typedef pair<int,int>PII; char p[N][N]; int st[N][N]; int n,T; int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}; int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1}; bool check(int i,int j) { for(int k = 0;k < 8;++k) { int x = i + dx[k]; int y = j + dy[k]; if(x >= 0&&x < n&&y >= 0&&y < n&&p[x][y] == '*') return false; } return true; } int bfs(int i,int j) { st[i][j] = true; int tot = 0; queue<PII>q; q.push({i,j}); while(q.size() != 0) { int x,y; tot ++; auto t = q.front(); q.pop(); if(!check(t.first,t.second)) continue; for(int k = 0;k < 8;++k) { x = t.first + dx[k]; y = t.second + dy[k]; if(x >= 0&&x < n&&y >= 0&&y < n&&p[x][y] == '.'&&!st[x][y]) { st[x][y] = true; q.push({x,y}); } } } return tot; } int main(){ cin >> T; for(int K = 1;K <= T; ++K){ memset(st,0,sizeof(st)); cin >> n; for(int i = 0;i < n; ++i) cin >> p[i]; int res = 0; for(int i = 0;i < n; ++i){ for(int j = 0;j < n; ++j){ if(p[i][j] == '.') res ++; if(p[i][j] == '.' && !st[i][j] && check(i,j)) res -= bfs(i,j) - 1; } } printf("Case #%d: %d\n",K,res); } } 2.动态网格

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

bfs + 染色法 原本的想法是：这个图在bfs染色之后，根据被改变点的性质，对点的前后左右可能因此相邻的颜色结果做并查集 但是一看数据范围纯暴力才1e7. 就可以每次改变图的状态，再去染色得到被染色的结果

#include<iostream> #include<queue> #include<cstring> using namespace std; const int N = 1005; typedef pair<int,int>PII; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, -1, 0, 1}; char p[N][N]; int res[N][N]; bool st[N][N]; int cnt = 0; int T,r,c; void bfs(int i,int j){ cnt++; res[i][j] = cnt; st[i][j] = true; queue<PII>q; q.push({i,j}); while(q.size() != 0) { auto t = q.front(); q.pop(); res[t.first][t.second] = cnt; for(int k = 0;k < 4;++k) { int x = t.first + dx[k]; int y = t.second + dy[k]; if(x >= 0&&x < r&&y>= 0&&y < c&&!st[x][y]&&p[x][y]=='1'){ st[x][y] = true; q.push({x,y}); } } } return; } int work(){ memset(st,0,sizeof(st)); cnt = 0; for(int i = 0;i < r;++i) for(int j = 0;j < c; ++j) if(p[i][j] == '1'&&!st[i][j]) bfs(i,j); return cnt; } int main(){ cin >> T; for(int K = 1;K <= T; ++K){ printf("Case #%d:\n",K); cin >> r >> c; for(int i = 0;i < r; ++i) cin >> p[i]; int Q; cin >> Q; while(Q--){ char t,z; int x,y; cin >> t; if(t == 'M'){ cin >> x >> y >> z; p[x][y] = z; } else cout << work() << endl; } } return 0; } 3.山峰和山谷

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′（山谷）。 如果周围不存在相邻区域，则同时将其视为山峰和山谷。 你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。

bfs + 染色法 转移条件：八个方向上和自己相同高度，以及不存在比自己矮（或高）的山峰。证明当前染色的连通块是山峰（或是山谷）

#include<iostream> #include<queue> #include<cstring> using namespace std; const int N = 1010; typedef pair<int,int> PII; int p[N][N]; bool st[N][N]; int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1}; int n; bool high,low; void bfs(int i,int j){ high = true; low = true; queue<PII>q; q.push({i,j}); st[i][j] = true; while(q.size() != 0){ auto t = q.front(); q.pop(); for(int K = 0;K < 8; ++K) { int x = t.first + dx[K]; int y = t.second + dy[K]; if(x < 1 || x > n || y < 1 || y > n) continue; if(p[x][y] == p[t.first][t.second] && !st[x][y]) { st[x][y] = true; q.push({x,y}); } if(p[x][y] > p[t.first][t.second]) high = false; if(p[x][y] < p[t.first][t.second]) low = false; } } } int main(){ cin >> n; for(int i = 1;i <=n; ++i) for(int j = 1;j <= n; ++j) cin >> p[i][j]; int a = 0,b = 0; for(int i = 1;i <=n; ++i) for(int j = 1;j <= n; ++j) if(!st[i][j]) { bfs(i,j); if(high) a++; if(low) b++; } cout << a << ' ' << b << endl; return 0; }