蒟蒻52分,求助!
查看原帖
蒟蒻52分,求助!
397712
dingyibo楼主2023/5/7 15:39
#include <bits/stdc++.h>

#define MAX_N 301

using namespace std;

int n, m;
char cm[MAX_N][MAX_N];
bool visits[MAX_N][MAX_N];
int offset[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

struct Point
{
    int x;
    int y;
    int step;
};

void SearchDoor( char c, int &nx, int &ny )
{
    int i, j;

    for(i=0;i<n;++i)
    {
        for(j=0;j<m;++j)
        {
            if(cm[i][j] == c && i != nx && j != ny)
            {
                nx = i;
                ny = j;
                return ;
            }
        }
    }
}

int BFS( int x, int y )
{
    queue<Point> q;
    Point t;
    t.x = x;
    t.y = y;
    t.step = 0;
    visits[x][y] = true;
    q.push(t);

    int min_step = 100000001;

    while(!q.empty())
    {
        Point p = q.front();
        q.pop();
        if(cm[p.x][p.y] == '=')
            return p.step;
        if(cm[p.x][p.y] >= 'A' && cm[p.x][p.y] <= 'Z')
            SearchDoor(cm[p.x][p.y], p.x, p.y);

        int i;
        int nx, ny;

        for(i=0;i<4;++i)
        {
            nx = p.x + offset[i][0];
            ny = p.y + offset[i][1];

            if(nx >= 0 && nx < n && ny >= 0 && ny < m && visits[nx][ny] == false && cm[nx][ny] != '#')
            {
                t.x = nx;
                t.y = ny;
                t.step = p.step+1;
                visits[nx][ny] = true;
                q.push(t);
            }
        }
    }

    return min_step;
}
int main()
{
    int i, j;
    int x, y;

    cin>>n>>m;

    for(i=0;i<n;++i)
    {
        for(j=0;j<m;++j)
        {
            cin>>cm[i][j];
            if(cm[i][j] == '@')
            {
                x = i;
                y = j;
            }
        }
    }

    cout<<BFS(x, y)<<endl;

    return 0;
}

求大佬解答

2023/5/7 15:39
加载中...