蓝桥杯基础技能树题解一（1~5）
1001-地、颜色、魔法
解：
在n*m的矩形中有两种点','和'#'，分别表示没用标记和有标记。被标记点完全包围的点（即从该点走到边界一定要经过至少一个标记点）同样视为被标记点。统计所有“标记点”的数量。
很基础的图遍历，用深度优先或者广度优先去遍历整张图都可以。由题意可以知道，一个点如果在矩阵的边界，那么它一定不是标记点。所以枚举每一个矩阵的边界点，若边界点是'.'，则以该点为起点遍历整张图并在原图中染色。我们将可以走到的点重新标记为‘@’，则剩下来的‘#’和'.'就都是标记点了。最后用循环遍历整张图完成操作。
对于存图，由于1<=n,m<=1e6，所以直接开二维数组mp[maxn][maxm]需要1e12的空间，此时已经超出了程序默认栈的大小，所以需要用一些巧妙的办法去存图。对于一维的字符串可以用string来存，二维字符串就可以用vector这样套娃了。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0,d[][2]={{0,1},{0,-1},{-1,0},{1,0}};
vector<string> mp;
bool check(int x,int y) { return 0<=x&&x<n&&0<=y&&y<m&&mp[x][y]=='.'; }
void dfs(int x,int y)
{
mp[x][y]='@';
for(int i=0;i<4;i++)
{
int tx=x+d[i][0];
int ty=y+d[i][1];
if(check(tx,ty))
dfs(tx,ty);
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
string s;
cin>>s;
mp.push_back(s);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if( (i==0||i==n-1) && (mp[i][j]=='.') )
dfs(i,j);
if( (j==0||j==m-1) && (i!=0||i!=n-1) && (mp[i][j]=='.') )
dfs(i,j);
}
}
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
ans+=(int)(mp[i][j]!='@');
cout<<ans<<endl;
return 0;
}
1002-扫雷
解：
扫雷都玩过吧。。。没有雷无限延伸，有数字则显示最边界的一个数字。即操作某一个格子以后，从该点开始遍历图，把所有的空格子都显示出来，并且在显示一个数字后返回。bfs和dfs都可以，记得标vis表示这个点是否走过了。
具体实现见代码，都是一样的东西就不细说了。注意若从下标0开始存图，存图坐标与输入坐标可能会差1，这是一个初学者常犯的错误。
#include<bits/stdc++.h>
using namespace std;
const int N=505;
char s[N][N];
int n,m,k,x,y,f;
void solve()
{
f=1;
cin>>n>>m>>k;
for(int i=0;i<n;i++)
cin>>s[i];
for(int i=1;i<=k;i++)
{
cin>>x>>y;
x--,y--;
if(!f)
continue;
if(s[x][y]=='.')
s[x][y]='0';
if(s[x][y]=='*')
{
cout<<"Game over in step "<<i<<endl;
f=0;
}
}
if(f)
for(int i=0;i<n;i++)
cout<<s[i]<<endl;
return;
}
int main()
{
int __;
cin>>__;
while(__--)
solve();
}
1003-wyh的迷宫
解：
又是个走迷宫题，写得多了应该就可以发现，对于这种图遍历问题都有差不多固定的解决方案，大同小异。
对于本题来说，有两种方案。方案一，从起点开始直接冲终点，把钥匙和门视为不可以走的墙，得到ans1。方案二，从起点去找钥匙，拿了钥匙去开门，再从门去终点，一共要有3次起止，加起来得到ans2。我们去min(ans1,ans2)即可得到答案。具体如何实现bfs不过多赘述，可以去看相关视频或博客自学板子。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int h,w,r0,r1,r2,r3;
int sx,sy,ex,ey,kx,ky,dx,dy;
char mp[N][N];
bool vis[N][N];
int d[][2]={{0,1},{0,-1},{-1,0},{1,0}};
struct node{int x,y,step;};
int bfs(int x1,int y1,int x2,int y2)
{
queue<node> q;
memset(vis,0,sizeof(vis));
vis[x1][y1]=1;
q.push({x1,y1,0});
while(!q.empty())
{
node tmp=q.front();
q.pop();
if(tmp.x==x2&&tmp.y==y2)
return tmp.step;
for(int i=0;i<4;i++)
{
int tx=tmp.x+d[i][0];
int ty=tmp.y+d[i][1];
if( 0<=tx&&tx<h && 0<=ty&&ty<w && mp[tx][ty]=='.'&&!vis[tx][ty] )
{
vis[tx][ty]=1;
q.push({tx,ty,tmp.step+1});
}
}
}
return -1;
}
int main()
{
cin>>h>>w;
for(int i=0;i<h;i++)
{
cin>>mp[i];
for(int j=0;j<w;j++)
{
if(mp[i][j]=='S')
sx=i,sy=j;
if(mp[i][j]=='E')
ex=i,ey=j;
if(mp[i][j]=='K')
kx=i,ky=j;
if(mp[i][j]=='D')
dx=i,dy=j;
}
}
mp[sx][sy]=mp[ex][ey]=mp[kx][ky]='.';
r0=bfs(sx,sy,ex,ey);//直接找终点
r1=bfs(sx,sy,kx,ky);//起点找钥匙
mp[dx][dy]='.';
r2=bfs(kx,ky,dx,dy);//钥匙找锁门
r3=bfs(dx,dy,ex,ey);//锁门找终点
if(r0==-1)
{
if(r1==-1||r2==-1||r3==-1)
puts("-1");
else
cout<<r1+r2+r3<<endl;
}
else
cout<<min(r0,r1+r2+r3)<<endl;
return 0;
}
1005-桃花
解：
本题给出了n个点和n-1条双向边，对于这样的一个图求最长的一条链的长度。因为这个图是一个树形图，所以求的东西有个名称叫树的直径。顾名思义，就是在树的两端各取一点，他们连起来最长就是树的直径。
不难观察到，假设树的其中一条直径由节点a,b作为端点构成，那么从图中的任意一个点k去找以k为起点的最长链，一定可以找点端点b(从b反向去推到k可以更好理解)。再从b去推最长链就可以找到节点a了。
对于实现这个推链的过程，在固定起点的时候，跑bfs或者dfs都可以。
综上，本题的解题思路变成了：从随机点（假设是点1）开始跑一遍搜索得到终点b，再从b开始跑一遍搜索得到终点a。搜索过程中维护max，最后输出即可。
另外本题有一个卡时间的地方，就是存图。如果使用vector v[maxn]这样vector存邻接表的方法去存图，很可能因为stl的巨大常数导致超时。所以推荐使用链式前向星去存图。邻接表可以靠评测机抖动卡过去，链式前的效率更高，省了400ms，乱杀。另外看到有清华爷写了一个更妙的办法，一并贴在下方供学习。
ps：图的存储包括了二维邻接矩阵，邻接表，链式前向星等等。建议自学。
#include<bits/stdc++.h>
const int N=1000009;
using namespace std;
typedef long long int ll;
struct as{
int y,next;
}a[2000009];
ll s[N],dis[N],ex=1,cnt=0,ans=-1;
bool vis[N];
void add(int x,int y)
{
a[++cnt].y=y;
a[cnt].next=s[x];
s[x]=cnt;
}
void bfs()
{
memset(vis,0,sizeof vis);
queue<int> p;
p.push(ex);
dis[ex]=1;
int x,y;
while(!p.empty())
{
x=p.front();
p.pop();
vis[x]=1;
if(ans<dis[x]){
ans=dis[x];
ex=x;
}
for(int i=s[x];i!=0;i=a[i].next)
{
y=a[i].y;
if(!vis[y])
{
dis[y]=dis[x]+1;
p.push(y);
}
}
}
}
int main()
{
int n,x,y;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
bfs();
bfs();
printf("%lld",ans);
return 0;
}
清华爷代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,k,h[1000005],ne[2000005],p[2000005],f[1000005],d[1000005];
void dfs(int x)
{
for(int i=h[x];i;i=ne[i])if(p[i]!=f[x])
{
f[p[i]]=x;
d[p[i]]=d[x]+1;
dfs(p[i]);
}
}
int main()
{
scanf("%d",&n);
for(i=1;i<n;i++)
{
scanf("%d%d",&j,&k);
p[++m]=k;
ne[m]=h[j];
h[j]=m;
p[++m]=j;
ne[m]=h[k];
h[k]=m;
}
dfs(1);
for(i=j=1;i<=n;i++)if(d[i]>d[j])j=i;
f[j]=d[j]=0;
dfs(j);
for(i=1,j=0;i<=n;i++)j=max(j,d[i]);
cout<<j+1<<endl;
return 0;
}
查看2道真题和解析