测试点4 传送点没有成对出现
查看原帖
测试点4 传送点没有成对出现
680697
lv__sc楼主2023/2/25 17:21

第四个测试点输入如下

19 24
########################
#@..A.#BR#RF#E...#.....#
#...#.##.##.####.#.###.#
#####BA#.##.#Q.#.#.#...#
#D...C#W.#FQ####...#.#.#
####C########D.E####.#.#
#...#...#....#W#...#.#.#
#.#.#.#.#.#...#..#.#.#.#
#.#...#...#..T#..#...#.#
#N##############.#####.#
#X#X#M#J#V###V.#.......#
#Z#Y#Y#M#J#########.####
#..#.#.#.##......#.....#
#.#...N#....#...#......#
#.#.####.####..#.......#
#.#......#....#........#
#.########.###.......###
#....................#T=
########################

结果是

112

通过代码如下



#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;

bool st[310][310] = {false};
map<char, PII> mp;
int dist[310][310];
string s[310];
int n, m;
map<PII, PII> tiao;

void bfs(int x, int y)
{
    int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
    st[x][y] = true;
    queue<PII> q;
    dist[x][y] = 0;
    q.push({x, y});
    while (!q.empty())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            x = t.first + dx[i];
            y = t.second + dy[i];
            if (!st[x][y] && x >= 0 && x < n && y >= 0 && y < m)
            {
                if (s[x][y] == '.' || s[x][y] == '=')
                {
                    dist[x][y] = dist[t.first][t.second] + 1;
                    //cout << x << " " << y << endl;
                    st[x][y] = 1;
                    q.push({x, y});
                } else if (s[x][y] >= 'A' && s[x][y] <= 'Z'&&tiao.contains({x,y}))
                {
                    //dist[x][y] = dist[t.first][t.second] + 1;
                    st[x][y] = 1;//起点标记到过,而终点标记不标记
                    int x1 = tiao[{x, y}].first;
                    int y1 = tiao[{x, y}].second;
                    x = x1, y = y1;
                    dist[x][y] = dist[t.first][t.second] + 1;
                    //cout << x << " " << y << endl;
                    q.push({x, y});
                }
            }
            if (s[x][y] == '=')
            {
                cout << dist[x][y];
                return;
            }
        }

    }
}


int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);


    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    int x, y;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] >= 'A' && s[i][j] <= 'Z')
            {
                if (mp.contains(s[i][j]))
                {
                    tiao[{i, j}] = {mp[s[i][j]].first, mp[s[i][j]].second};
                    tiao[{mp[s[i][j]].first, mp[s[i][j]].second}] = {i, j};
                } else
                {
                    mp[s[i][j]] = {i, j};
                }
            }
            if (s[i][j] == '@')
                x = i, y = j;
        }
    bfs(x, y);


    return 0;
}

一直卡在这个测试点,其他测试点也有类似的情况吗,还有单个出现的z是当作玉米还是草地呢

2023/2/25 17:21
加载中...