CSES: Labyrinth

CSES: Labyrinth

USACO.guide上的 easy: CSES - Labyrinth

这道确实简单，但是好久没写图论了生疏了还搞了一整子的😓.

思路

思路就是从A跑BFS到B，非常简单。所以现在就可以开始写了：

代码1

//
// Created by Chixiyu on 1/28/2024.
//
#include <bits/stdc++.h>
using namespace std;


const int N = 1010;
string graph[N];
int n, m;
bool vis[N][N];

bool valid(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m || graph[x][y] == '#' || vis[x][y]) return false;
    return true;
}

struct point {
    int x;
    int y;
    int step;
    string direction;
};

int main() {
    cin >> n >> m;
    pair<int, int> start;
    for (int i = 0; i < n; ++i) {
        cin >> graph[i];
        for (int j = 0; j < m; ++j) {
            if (graph[i][j] == 'A') {
                start = make_pair(i, j);
            }
        }
    }
    pair<int, string> ans;
    queue<point> q;
    q.push({start.first, start.second, 0, ""});
    bool flag = false; // "YES" or "NO"
    while (!q.empty()) {
        point current = q.front();
        vis[current.x][current.y] = true;
        q.pop();
        if (graph[current.x][current.y] == 'B') {
            cout << "YES" << endl << current.step << endl << current.direction;
            flag = true;
            break;
        }

        current.direction.push_back('D');
        if (valid(current.x + 1, current.y)) {
            q.push({current.x + 1, current.y, current.step + 1, current.direction});
            vis[current.x + 1][current.y] = true;
        }
        current.direction.pop_back();
        current.direction.push_back('U');
        if (valid(current.x - 1, current.y)) {
            q.push({current.x - 1, current.y, current.step + 1, current.direction});
            vis[current.x - 1][current.y] = true;
        }
        current.direction.pop_back();
        current.direction.push_back('L');
        if (valid(current.x, current.y - 1)) {
            q.push({current.x, current.y - 1, current.step + 1, current.direction});
            vis[current.x][current.y - 1] = true;
        }
        current.direction.pop_back();
        current.direction.push_back('R');
        if (valid(current.x, current.y + 1)) {
            q.push({current.x, current.y + 1, current.step + 1, current.direction});
            vis[current.x][current.y + 1] = true;
        }
    }
    // output

    if (!flag) { cout << "NO" << endl; }
    return 0;
}

但是这样子会发现有一个点超时了，？？？

可能是BFS过程中每一步都保存了完整的点，我们可以只保存上次的那个 point的地址，使用指针在找到 B之后，直接用指针链回去反推出完整路径（记得翻转）。

代码2

成功AC

//
// Created by Chixiyu on 1/29/2024.
//
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
char graph[N][N]; // Using a character array is more space-efficient than std::string
bool vis[N][N];
int n, m;
int dx[] = {1, -1, 0, 0}; // Directions: down, up, right, left
int dy[] = {0, 0, 1, -1};
char dir[] = {'D', 'U', 'R', 'L'}; // Corresponding characters for directions

struct point {
    int x, y, step;
    point* prev; // Pointer to previous point for path reconstruction
    char move; // Move taken to get to this point
};

bool valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && graph[x][y] != '#' && !vis[x][y];
}

string reconstruct_path(point* p) {
    string path;
    while (p->prev) {
        path.push_back(p->move);
        p = p->prev;
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    pair<int, int> start, end;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> graph[i][j];
            if (graph[i][j] == 'A') {
                start = {i, j};
            } else if (graph[i][j] == 'B') {
                end = {i, j};
            }
        }
    }

    queue<point> q;
    q.push({start.first, start.second, 0, nullptr, 0});
    vis[start.first][start.second] = true;

    bool found = false;
    while (!q.empty()) {
        point current = q.front();
        q.pop();

        if (current.x == end.first && current.y == end.second) {
            cout << "YES\n" << current.step << "\n" << reconstruct_path(&current);
            found = true;
            break;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = current.x + dx[i], ny = current.y + dy[i];
            if (valid(nx, ny)) {
                vis[nx][ny] = true;
                q.push({nx, ny, current.step + 1, new point(current), dir[i]});
            }
        }
    }

    if (!found) {
        cout << "NO\n";
    }

    return 0;
}