蓝桥杯每日一题（BFS）

1562 微博转发

开始思路错误点：在用拉链法保存关注信息的时候，因为要看一个用户发的有多少转发的，所以要以用户为坑位，所有关注这个坑位的用户为链表。（开始弄反了）

e数组存某个用户的idx，ne是某个节点在链表上的下一个，h是坑位。

st状态数组的参数是用户，而不是idx

#include<bits/stdc++.h>
using namespace std;
//1562 微博转发
const int N=1e3+10;
int n,l;
//拉链法存储
int e[N],idx,ne[N],h[N];
bool st[N];
//e某个idx对应的用户是谁
//ne 这个用户和其他人是否被i同时关注
//h代表某个用户的关注列表的链表尾部
void add(int u,int x)
{
   // 把某个被关注的用户加入到某个用户的链表中
    e[idx]=x,ne[idx]=h[u],h[u]=idx++;
}
 
int bfs(int s)//找某个节点的第l层关注的用户个数
{
    //之前都是只要有后继就加入到队列中
    //如何实现到规定的层的位置就终止呢
    //就是L层循环:每次循环都控制向外延伸一层
    memset(st,0,sizeof(st));
    queue<int>q;
    q.push(s);
    st[s]=1;
    int res=0;//前l层有多少个点
    for(int i=1;i<=l;i++)//向前走l层
    {
        int num=q.size();
        //num就是上一次循环扩展出来的点
        while(num--)
        {
            int t=q.front();
            q.pop();
            for(int j=h[t];j!=-1;j=ne[j])
            {
                if(!st[e[j]])
                {
                    q.push(e[j]);
                    res++;
                    st[e[j]]=1;
                }
            }
        }
    }
    return res;
 
}
int main()
{
    cin>>n>>l;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        while(x--)
        {
            int u;
            cin>>u;
            add(u,i);//i关注了u
        }
    }
        int qu;
        cin>>qu;
        while(qu--)
        {
            int user;
            cin>>user;
            cout<<bfs(user)<<endl;
        }
 
 
 
}

//844走迷宫

自己是用pair并且second放走的步数，内存超限了。

下面是自己的做法

#include<bits/stdc++.h>
using namespace std;
//844走迷宫
typedef pair<int,int>PII;
typedef pair<PII,int> PIII;
const int N=100;
int p[N][N];
int n,m;
int s[4]={0,1,0,-1};
int z[4]={1,0,-1,0};
int dfs()
{
    queue<PIII>q;
    q.push({{1,1},0});
    while(!q.empty())
    {
        PIII t=q.front();
        q.pop();
 
        PII zuo=t.first;
        int x=zuo.first;
        int y=zuo.second;
        for(int i=0;i<4;i++)
        {
            if(x+z[i]>=1&&x+z[i]<=n&&y+s[i]>=1&&y+s[i]<=m&&!p[x+z[i]][y+s[i]])
            {
                q.push({{x+z[i],y+s[i]},t.second+1});
                if(x+z[i]==n&&y+s[i]==m)
                {
                    //cout<<t.second+1<<endl;
                    return t.second+1;
                }
            }
        }
 
    }
 
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int num;
            cin>>num;
            if(num)p[i][j]=1;
        }
    }
   cout<< dfs();
}
 

y做法：直接使用一个二维数组存某个坐标到达的时候走的步数。

845 八数码 

在bfs求最短路的问题中，重点是怎么保存状态，y的做法：把矩阵转化为字符串，从初始位置到这个状态走的距离就是变化的次数

太巧妙了；

//看完y思路之后，最后怎么都是输出不对，最后找到是swap（还原的那个swap）应该也在if条件中，就是在4层的for循环中不一定都符合不越界的要求。

#include<bits/stdc++.h>
using namespace std;
//845 八数码
//既可以存状态，又可以存步数
unordered_map<string ,int>d;//记录到这个状态转换了多少次
queue<string>q;//所有的状态
string start="12345678x";
int ss[4]={-1, 0, 1, 0},z[4]={0, 1, 0, -1};
int bfs(string s)
{
  q.push(s);
  d[s]=0;
  while(q.size())
  {
      string t=q.front();
      q.pop();
      int p=t.find('x');
      int y=p/3;
      int x=p%3;
      int dis=d[t];
      if(t==start)return d[t];
      for(int i=0;i<4;i++)
      {
        //  cout<<" ********"<<endl;
          int xx=x+z[i];
          int yy=y+ss[i];
          //cout<<xx<<" "<<yy<<" "<<"si::"<<ss[i]<<endl;
          if(xx>=0&&xx<3&&yy>=0&&yy<3)
          {
              swap(t[p],t[yy*3+xx]);
              //cout<<"yun"<<endl;
              if(!d.count(t))
              {
 
                  d[t]=dis+1;
                  q.push(t);
              }
              swap(t[p],t[yy*3+xx]);
 
          }
         //if(t==start)return d[t];
 
      }
  }
  return -1;
}
 
 
int main()
{
    string s;
    for(int i=0;i<9;i++)
    {
        string c;
        cin>>c;
        s+=c;
    }
    //cout<<s<<endl;
    cout<<bfs(s)<<endl;
 
 
 
}

//1233全球变暖

自己做的WA，先用 bfs看有几个岛屿，淹没操作后，再用bfs看。

#include<bits/stdc++.h>
using namespace std;
//1233 全球变暖
typedef pair<int,int>PII;
const int N=1010;
int n;
int p[N][N],f[N][N];
int st[N][N];
int s[4]={1,0,0,-1},z[4]={0,1,-1,0};
int bfs()
{
    int cnt=0;
    memset(st,0,sizeof(st));
    queue<PII>q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
 
            if(!st[i][j]&&p[i][j])//没有被访问过的一片陆地
            {
             //  cout<<"find that match if"<<endl;
               st[i][j]=1;
               cnt++;
               //cout<<"cnt "<<cnt<<endl;
               q.push({i,j});
               while(q.size())
               {
                   PII t=q.front();
                   //cout<<q.front().first<<" "<<q.front().second<<endl;
                   q.pop();
                   for(int k=0;k<4;k++)
                   {
                       int x=t.first+s[k];
                       int y=t.second+z[k];
                       if(x>=1&&x<=n&&y>=1&&y<=n&&p[x][y]&&!st[x][y])
                       {
                           q.push({x,y});
                           st[x][y]=1;
                       }
                   }
               }
            }
        }
    }
    return cnt;
}
 
 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char c;
            cin>>c;
            if(c=='#')p[i][j]=1,f[i][j]=1;
        }
    }
    
    //查看有几个岛屿
    int precnt=bfs();
    //淹没
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!f[i][j])//如果本来是一个海域
            {
                for(int k=0;k<4;k++)
                   {
                       //cout<<"dawn"<<endl;
                       int x=i+s[k];
                       int y=j+z[k];
                       if(x>=1&&x<=n&&y>=1&&y<=n&&p[x][y])
                       {
                           p[x][y]=0;//被淹没
                       }
                   }
            }
        }
    }
 
    //还有几个岛屿
    int poscnt=bfs();
    int num=precnt-poscnt;
    cout<<num<<endl;
 
}

y是在bfs的时候就在4的for循环中判断，这个连通块是否被淹没，是就加加。最后根据这个连通块的节点个数和被淹没的节点个数判断这个岛屿是否被淹没