本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
洛谷：AT_abc460_d [ABC460D] Repeatedly Repainting - 洛谷
【题目描述】
There is a grid withH HHrows andW WWcolumns. The cell at thei ii-th row from the top and thej jj-th column from the left is called cell( i , j ) (i, j)(i,j).
Every cell is colored white or black. The grid is described byH HHstringsS 1 , S 2 , … , S H S_1, S_2, \ldots, S_HS1,S2,…,SH, each of lengthW WW. If thej jj-th character ofS i S_iSiis., cell( i , j ) (i, j)(i,j)is white; if thej jj-th character ofS i S_iSiis#, cell( i , j ) (i, j)(i,j)is black.
You perform the following operation10 100 10^{100}10100times.
- Simultaneously apply the following rules to all cells.
- A cell that is white before the operation becomes black if and only if there exists at least one black cell adjacent to it. Here, cells( x , y ) (x, y)(x,y)and( x ′ , y ′ ) (x', y')(x′,y′)are adjacent if and only if one of them is within the8 88-neighborhood of the other, that is,max ( ∣ x − x ′ ∣ , ∣ y − y ′ ∣ ) = 1 \max(|x-x'|, |y-y'|) = 1max(∣x−x′∣,∣y−y′∣)=1.
- A cell that is black before the operation becomes white.
Find the color of each cell after the operations.
有一个H HH行W WW列的网格。从上往下第i ii行、从左往右第j jj列的单元格称为单元格( i , j ) (i, j)(i,j)。
每个单元格被涂成白色或黑色。网格由H HH个字符串S 1 , S 2 , … , S H S_1, S_2, \ldots, S_HS1,S2,…,SH描述，每个字符串长度为W WW。如果S i S_iSi的第j jj个字符是.，则单元格( i , j ) (i, j)(i,j)是白色的；如果是#，则单元格( i , j ) (i, j)(i,j)是黑色的。
你将执行以下操作10 100 10^{100}10100次。
- 同时对所有单元格应用以下规则。
- 在操作前为白色的单元格变为黑色，当且仅当存在至少一个与之相邻的黑色单元格。这里，单元格( x , y ) (x, y)(x,y)和( x ′ , y ′ ) (x', y')(x′,y′)相邻当且仅当其中一个在另一个的8 88邻域内，即max ( ∣ x − x ′ ∣ , ∣ y − y ′ ∣ ) = 1 \max(|x-x'|, |y-y'|) = 1max(∣x−x′∣,∣y−y′∣)=1。
- 在操作前为黑色的单元格变为白色。
求操作后每个单元格的颜色。
【输入】
The input is given from Standard Input in the following format:
H HHW WW
S 1 S_1S1
S 2 S_2S2
⋮ \vdots⋮
S H S_HSH
【输出】
OutputH HHlines.
Output one string of lengthW WWconsisting of.and#per line.
Thej jj-th character of thei ii-th line should be.if cell( i , j ) (i, j)(i,j)is white after10 100 10^{100}10100operations, and#if it is black.
【输入样例】
3 4 #.#. .#.. #...【输出样例】
#.#. .#.. #..#【算法标签】
#普及plus
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;constintN=1000005;inth,w;// 网格的行数和列数intdx[8]={-1,-1,-1,0,0,1,1,1};// 八个方向的x偏移intdy[8]={-1,0,1,-1,1,-1,0,1};// 八个方向的y偏移vector<string>s;// 存储网格vector<vector<int>>f;// 存储每个位置的距离voidbfs()// 广度优先搜索计算距离{queue<PII>q;for(inti=1;i<=h;i++)// 初始化队列for(intj=1;j<=w;j++){if(s[i][j]=='#')// 如果当前位置是障碍{q.push({i,j});// 入队f[i][j]=0;// 距离为0}}while(!q.empty())// 当队列不为空{intx=q.front().first,y=q.front().second;q.pop();// 出队for(inti=0;i<8;i++)// 遍历八个方向{intnx=x+dx[i],ny=y+dy[i];if(nx<1||nx>h||ny<1||ny>w||f[nx][ny]!=-1)// 越界或已访问continue;f[nx][ny]=f[x][y]+1;// 更新距离q.push({nx,ny});// 入队}}}intmain(){cin>>h>>w;// 输入行数和列数s.resize(h+1);f.assign(h+1,vector<int>(w+1,-1));// 初始化距离数组为-1for(inti=1;i<=h;i++)// 输入网格{cin>>s[i];s[i]=" "+s[i];// 在字符串前加空格，使下标从1开始}queue<PII>q;for(inti=1;i<=h;i++)// 寻找内部障碍for(intj=1;j<=w;j++){if(s[i][j]=='#')// 如果当前位置是障碍{boolflag=1;for(intk=0;k<8;k++)// 检查八个方向{intnx=i+dx[k],ny=j+dy[k];if(nx<1||nx>h||ny<1||ny>w)// 越界continue;if(s[nx][ny]=='.')// 如果邻居是空地{flag=0;// 不是内部障碍break;}}if(flag)// 如果是内部障碍q.push({i,j});}}while(!q.empty())// 移除内部障碍{intx=q.front().first,y=q.front().second;q.pop();s[x][y]='.';// 将内部障碍变为空地}bfs();// 计算距离for(inti=1;i<=h;i++)// 输出结果{for(intj=1;j<=w;j++){if(f[i][j]%2==0)// 如果距离是偶数cout<<"#";elsecout<<".";}cout<<endl;}return0;}【运行结果】
3 4 #.#. .#.. #... #.#. .#.. #..#
