【搜索】—— 多源BFS + 最小步数模型

---

AcWing 173. 矩阵距离  （多源BFS）

 

输入样例：

3 4
0001
0011
0110

输出样例：

3 2 1 0
2 1 0 0
1 0 0 1

---

在多源最短路的问题中，如果我们采用每个点的单源最短路，很大概率会超时 

所以我们需要用到一个 “超级源点” 思想

建立一个虚拟源点，将所有的起点和这个虚拟源点连一条边为 0 的边，然后展开单源最短路 

---

#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

#define x first
#define y second

const int N = 1010, M = N * N;

typedef pair<int,int> PII;

int n, m;
char g[N][N];
PII q[M];
int dist[N][N];

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

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) scanf("%s", g[i]);
    
    bfs();
    
    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < m; j ++ )
            printf("%d ", dist[i][j]);
        cout << endl;
    }
    
    return 0;
        
}

---

 AcWing 1107. 魔板（最小步数模型）

 

输入样例：

2 6 8 4 5 7 3 1

输出样例：

7
BCABCCB

---

这是将整个棋盘看做是一个状态，通过不同的操作来实现状态间的转移 

存放一个状态，我们使用的是哈希法  <unordered_map>

---

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

using namespace std;

char g[2][4];
unordered_map<string, pair<char, string>> pre;
unordered_map<string, int> dist;

void set(string state)
{
    for (int i = 0; i < 4; i ++ ) g[0][i] = state[i];
    for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i];
}

string get()
{
    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();
}

string move1(string state)
{
    set(state);
    int v0 = g[0][3], v1 = g[1][3];
    for (int i = 3; i >= 0; i -- )
    {
        g[0][i] = g[0][i - 1];
        g[1][i] = g[1][i - 1];
    }
    g[0][0] = v0, g[1][0] = v1;
    return get();
}

string move2(string state)
{
    set(state);
    int 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();
}

int bfs(string start, string end)
{
    if (start == end) return 0;

    queue<string> q;
    q.push(start);
    dist[start] = 0;

    while (!q.empty())
    {
        auto 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 ++ )
            if (!dist.count(m[i]))
            {
                dist[m[i]] = dist[t] + 1;
                pre[m[i]] = {'A' + i, t};
                q.push(m[i]);
                if (m[i] == end) return dist[end];
            }
    }

    return -1;
}

int main()
{
    int x;
    string start, end;
    for (int i = 0; i < 8; i ++ )
    {
        cin >> x;
        end += char(x + '0');
    }

    for (int i = 1; i <= 8; i ++ ) start += char('0' + i);

    int step = bfs(start, end);

    cout << step << endl;

    string res;
    while (end != start)
    {
        res += pre[end].first;
        end = pre[end].second;
    }

    reverse(res.begin(), res.end());

    if (step > 0) cout << res << endl;

    return 0;
}

---

AcWing 175. 电路维修 （双端队列广搜）

输入样例：

1
3 5
\\/\\
\\///
/\\\\

输出样例：

1

 

 

---

【搜索】—— 双端队列广搜_玄澈_的博客-CSDN博客_双端队列搜索 

 

---

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

#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 510;

int n,m;
char g[N][N];
int dist[N][N];;
deque<PII> q;

int bfs()
{
    memset(dist,0x3f,sizeof dist);
    q.push_front({0,0});
    dist[0][0]=0;
    int dx[]={-1,-1,1,1},dy[]={-1,1,1,-1};
    int ix[]={-1,-1,0,0},iy[]={-1,0,0,-1};

    char s[]="\\/\\/";

    while(q.size())
    {
        PII t=q.front();
        q.pop_front();
        for(int i=0;i<4;i++)
        {
            int a=t.x+dx[i],b=t.y+dy[i];
            int aa=t.x+ix[i],bb=t.y+iy[i];
            if(a<0||a>n||b<0||b>m) continue;
            int d = dist[t.x][t.y]+(g[aa][bb]!=s[i]);
            if (d < dist[a][b])
            {
                dist[a][b] = d;

                if (g[aa][bb] != s[i]) q.push_back({a, b});
                else q.push_front({a, b});
            }
        }
    }
    return dist[n][m];
}


int main()
{   int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
        if((n+m)%2==1) 
        {
            puts("NO SOLUTION");
            continue;
        }                
        cout<<bfs()<<endl;
    }
    return 0;
}