46分求助,其它都是WA
查看原帖
46分求助,其它都是WA
319478
zhibuba楼主2020/8/12 22:18
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <cctype>

using namespace std;

struct Point
{
    int x, y;
    bool operator<(const Point & b) const {return tie(x, y) < tie(b.x, b.y);}
};

struct Hash
{
    size_t operator()(Point a)
    {return a.x * 300 + a.y;}
};

const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {-1, 0, 1, 0};
char Matrix[301][301];
int Arrive[301][301];
map<Point, Point> transit;
map<char, Point> tmp;
queue<Point> Q;
bool used[256];

int main()
{
    fill(&Arrive[0][0], &Arrive[300][300], -1);
    int N, M;
    Point start;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> Matrix[i][j];
            if (Matrix[i][j] == '@')
                start = {i,j};
            else if (isalpha(Matrix[i][j]))
            {
                auto p = tmp.find(Matrix[i][j]);
                if (p != tmp.end())
                {
                    transit.insert({tmp[Matrix[i][j]], {i, j}});
                    transit.insert({{i, j}, {tmp[Matrix[i][j]]}});
                }
                else
                    tmp.insert({Matrix[i][j], {i, j}});
            }
        }
    }
    Q.push(start), Arrive[start.x][start.y] = 0;
    while (!Q.empty())
    {
        Point A = Q.front();
        Q.pop();
        char c = Matrix[A.x][A.y];
        if (c == '=')
        {
            cout << Arrive[A.x][A.y];
            return 0;
        }
        else if (isalpha(c) && !used[c])
        {
            Point B = transit[A];
            if (Arrive[B.x][B.y] == -1)
            {
                used[c] = true;;
                Arrive[B.x][B.y] = Arrive[A.x][A.y];
                Q.push(B);
            }
        }
        else
        {
            for (int i = 0; i < 4; i++)
            {
                int x = A.x + dx[i], y = A.y + dy[i];
                if (x >= 1 && x <= N && y >= 1 && y <= M && Matrix[x][y] != '#' && Arrive[x][y] == -1)
                {
                    Arrive[x][y] = Arrive[A.x][A.y] + 1;
                    Q.push({x, y});
                }
            }
        }
    } 
}
2020/8/12 22:18
加载中...