(BFS) template + example (maze, eight digits)

Labyrinth

Given a  n×mn×m  A two-dimensional array of integers , Used to represent a maze , The array contains only  00  or  11, among  00  Means the way to go ,11  Indicates an impassable wall .

first , There is a man in the upper left corner  (1,1)(1,1)  It's about , It is known that the person can go up every time 、 Next 、 Left 、 Move a position in any right direction .

Excuse me, , The person moves from the upper left corner to the lower right corner  (n,m)(n,m)  It's about , At least how many times you need to move .

Data assurance  (1,1)(1,1)  Place and  (n,m)(n,m)  The number at is  00, And there must be at least one path .

Input format

The first line contains two integers  nn  and  mm.

Next  nn  That's ok , Each row contains  mm  It's an integer （00  or  11）, Represents a complete two-dimensional array .

Output format

Output an integer , Represents the minimum number of moves from the upper left corner to the lower right corner .

Data range

1≤n,m≤1001≤n,m≤100

sample input ：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

sample output ：

8

#include <bits/stdc++.h>
using namespace std;
queue <pair<int,int>> q;
const int N=110;
int mp[N][N];
int d[N][N];
int n,m;
int bfs()
{
    memset(d,-1,sizeof(d));
    d[1][1]=0;
    q.push({1,1});
    int dx[]={-1,0,0,1};
    int dy[]={0,1,-1,0};
    while(!q.empty())
    {
        for(int i=0;i<=3;i++)
        {
            auto t=q.front();
            int x=t.first+dx[i],y=t.second+dy[i];
            if(x>=1&&x<=n&&y>=1&&y<=m&&d[x][y]==-1&&mp[x][y]==0)
            {
                mp[x][y]=0;
                d[x][y]=d[t.first][t.second]+1;
                q.push({x,y});
            }

        }
        q.pop();
    }
    return d[n][m];
}
int main()
{
    int i,j;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%d",&mp[i][j]);
        }
    }
    printf("%d",bfs());
    return 0;
}

2. Eight digital  

In a  3×33×3  In the grid ,1∼81∼8  this  88  A number and a  x  It happens to be distributed here without weight or leakage  3×33×3  In the grid .

for example ：

1 2 3
x 4 6
7 5 8

During the game , You can put  x  Above it 、 Next 、 Left 、 Digital exchange in one of the four right directions （ If there is ）.

Our goal is to exchange , Make the grid arranged as follows （ It is called correct arrangement ）：

1 2 3
4 5 6
7 8 x

for example , In the example, the graph can be created by making  x  And right 、 Next 、 The numbers in the right three directions are exchanged successfully and arranged correctly .

The exchange process is as follows ：

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

Now? , Give you an initial grid , Please find out at least how many exchanges are needed to get the correct arrangement .

Input format

Input takes up a line , take  3×33×3  The initial grid of .

for example , If the initial mesh is as follows ：

1 2 3 
x 4 6 
7 5 8 

Then enter ：1 2 3 x 4 6 7 5 8

Output format

Output takes up one line , Contains an integer , Indicates the minimum number of exchanges .

If no solution exists , The output  −1−1.

sample input ：

2  3  4  1  5  x  7  6  8

sample output

19

 

 

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

using namespace std;

int bfs(string state)
{
    queue<string> q;
    unordered_map<string, int> d;

    q.push(state);
    d[state] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    string end = "12345678x";
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        if (t == end) return d[t];

        int distance = d[t];
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[a * 3 + b], t[k]);
                if (!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[a * 3 + b], t[k]);
            }
        }
    }

    return -1;
}

int main()
{
    char s[2];

    string state;
    for (int i = 0; i < 9; i ++ )
    {
        cin >> s;
        state += *s;
    }

    cout << bfs(state) << endl;

    return 0;
}