萌新求助 bfs
查看原帖
萌新求助 bfs
107253
Water_Cows楼主2020/10/1 22:02

现在菜到连 bfs 都不会了。。。。。

#include <iostream>
#include <queue>
using namespace std;

const int N = 300 + 7;

int n, m, flag;
int a[N][N], ans[N][N];
pair < int, int > go[N][N];
int q1, q2, x1, y1, x2, y2, z1, z2;

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

queue < pair < int, int > > q;
pair < int, int > chh[N];

inline void bfs(int q1, int q2)
{
    q.push(make_pair(q1, q2));
    
    while(!q.empty())
    {
        if(flag) break;

        int x = q.front().first, y = q.front().second;
        q.pop();
        a[x][y] = 1;

        //cout << x << ' ' << y << endl;
        
        for(int i=0; i<4; i++)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];

            if(tx < 1 || ty < 1) continue;
            if(tx > n || ty > m) continue;
            if(a[tx][ty]) continue;

            ans[tx][ty] = ans[x][y] + 1;
            if(tx == z1 && ty == z2)
            {
                cout << ans[tx][ty] << endl;
                flag = 1;
            }
            q.push(make_pair(tx, ty));
        }
        int nowx = go[x][y].first, nowy = go[x][y].second;
        if(nowx && nowy)
            ans[nowx][nowy] = ans[x][y], q.push(make_pair(nowx, nowy));
    }
}

int main()
{
    freopen("1.in", "r", stdin);
    
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);


    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            char ch;
            cin >> ch;
            if(ch == '=')
                z1 = i, z2 = j;
            if(ch == '#')
                a[i][j] = 1;
            if(ch == '.')
                ;

            if(ch >= 'A' && ch <= 'Z')
            {
                if(chh[ch].first)
                {
                    go[chh[ch].first][chh[ch].second] = make_pair(i, j);
                    go[i][j] = chh[ch];
                }
                else
                    chh[ch] = make_pair(i, j);
            }
            if(ch == '@')
                q1 = i, q2 = j, a[i][j] = 1;
        }
    }
    
    // cout << x1 << ' ' << y1 << endl;
    // cout << x2 << ' ' << y2 << endl;
    // cout << q1 << ' ' << q2 << endl;
    // cout << z1 << ' ' << z2 << endl;

    bfs(q1, q2);
}
2020/10/1 22:02
加载中...