跳到主要内容

BFS中的多源BFS-双端队列BFS

AcWing 173. 矩阵距离​

题目链接：https://www.acwing.com/problem/content/175/

思路​

多源BFS问题：

  • 多源BFS时有从多个源点出发的bfs算法,只需要将多个源点都连一条边权为0的边到虚拟源点,那么问题就等价于从虚拟源点开始BFS。
  • 一开始直接将所有源点加入BFS的队列即可.

本题中：

  • 将所有为1的点直接加入bfs队列，向外搜索，由bfs性质到达的点一定离虚拟源点最短,而到虚拟源点的距离 == 到1点的距离,故最短。

代码​

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define sc scanf
#define pr printf

const int N = 1010, M = N * N;
int n, m;
char g[N][N];
PII q[M];
int dist[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void bfs()
{
    memset(dist, -1, sizeof dist);
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (g[i][j] == '1')
            {
                dist[i][j] = 0;
                q[++tt] = {i, j};
            }
    while (hh <= tt)
    {
        PII t = q[hh++];
        for (int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 1 || a > n || b < 1 || b > m)
                continue;
            if (dist[a][b] != -1)
                continue;
            dist[a][b] = dist[t.x][t.y] + 1;
            q[++tt] = {a, b};
        }
    }
}

int main()
{
    sc("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        sc("%s", g[i] + 1);
    bfs();
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            pr("%d ",dist[i][j]);
        pr("\n");
    }
    return 0;
}

AcWing 1107. 魔板​

题目链接：https://www.acwing.com/problem/content/1109/

思路​

简单

代码​

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>
#include <unordered_map>
#include <queue>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
#define sc scanf
#define pr printf

char g[2][4];
unordered_map<string, int> dist;
unordered_map<string, pair<char, string>> pre;
queue<string> q;
void set(string state){
    for(int i=0;i<4;i++) g[0][i]=state[i];
    for(int i=3,j=4;i>=0;i--,j++) g[1][i]=state[j];
}
string get(string state){
    string res;
    for(int i=0;i<4;i++) res+=g[0][i];
    for(int i=3;i>=0;i--) res+=g[1][i];
    return res;
}
string move0(string state) {
    set(state);
    for(int i=0;i<4;i++) swap(g[0][i],g[1][i]);
    return get(state);
}
string move1(string state) {
    set(state);
    char v0=g[0][3],v1=g[1][3];
    for(int i=3;i>0;i--)
        for(int j=0;j<2;j++)
            g[j][i]=g[j][i-1];
    g[0][0]=v0,g[1][0]=v1;
    return get(state);
}
string move2(string state) {
    set(state);
    char v=g[0][1];
    g[0][1]=g[1][1];
    g[1][1]=g[1][2];
    g[1][2]=g[0][2];
    g[0][2]=v;
    return get(state);
}

void bfs(string start, string end)
{
    if (start == end)
        return;
    q.push(start);
    dist[start] = 0;
    while (q.size())
    {
        string t = q.front();
        q.pop();
        string m[3];
        m[0] = move0(t);
        m[1] = move1(t);
        m[2] = move2(t);
        for (int i = 0; i < 3; i++)
        {
            string a = m[i];
            if (dist.count(a) == 0)
            {
                dist[a] = dist[t] + 1;
                pre[a] = {char(i + 'A'), t};
                if (a == end)
                    break;
                q.push(a);
            }
        }
    }
}

int main()
{
    int x;
    string start, end; // end为读入,start为最终的状态 12345678
    for (int i = 0; i < 8; i++)
    {
        cin >> x;
        end += char(x + '0'); //将数字x转为ascii值对应的x
    }
    for (int i = 1; i <= 8; i++)
        start += char(i + '0');
    bfs(start, end);
    cout << dist[end] << endl;
    string res;
    while (end != start)
    {
        res += pre[end].x;
        end = pre[end].y;
    }
    reverse(res.begin(), res.end());
    if (res.size())
        cout << res << endl;
    return 0;
}

AcWing 175. 电路维修​

题目链接：https://www.acwing.com/problem/content/177/

思路​

双端队列：双端队列主要解决图中边的权值只有0或者1的最短路问题 操作：每次从队头取出元素，并进行拓展其他元素时

  • 若拓展某一元素的边权是0，则将该元素插入到队头
  • 若拓展某一元素的边权是1，则将该元素插入到队尾

必须在出队时才知道每个点最终的最小值

数组char cs[] = "\\/\\/";的作用： cs数组其实就是判断从某点到下一个点时经过的方格中的线是否和预期中的一样,初始时的 ‘\‘ ‘/’ ‘\‘ ‘/’其实就是从1号2号3号4号点过来时经过的方格联通时的状态,如果一样w=0否则w=1

代码​

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<ctime>
#include<deque>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define sc scanf
#define pr printf

const int N=510,M=N*N;
int n,m;
char g[N][N];
int dist[N][N];
bool st[N][N];

int bfs()
{
    deque<PII> q;
    memset(st,0,sizeof st);
    memset(dist,0x3f,sizeof dist);

    char cs[5]="\\/\\/";
    int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1};  
    int ix[]={-1,-1,0,0},iy[]={-1,0,0,-1};

    dist[0][0]=0;
    q.push_back({0,0});
    while (q.size())
    {
        PII t=q.front();q.pop_front();
        int x=t.x, y=t.y;
        if(x==n&&y==m) return dist[x][y];
        if(st[x][y]) continue;
        st[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<0||a>n||b<0||b>m) continue;//越界
            int ga=x+ix[i],gb=y+iy[i];
            int w=g[ga][gb]!=cs[i];
            int d=dist[x][y]+w;
            if(d<=dist[a][b])
            {
                dist[a][b]=d;
                if(!w) q.push_back({a,b});
                else q.push_back({a,b});
            }
        }
    }
    return dist[n][m];
    
}

int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>g[i];
        if(n+m&1) puts("NO SOLUTION");
        else pr("%d\n",bfs());
    }
    return 0;
}

0%