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;
}