8 条题解

  • 0
    @ 2025-1-5 16:45:39
    // https://dashoj.com/p/84
    // 1 可走 0 不可走
    #include <bits/stdc++.h>
    
    #define N 20
    using namespace std;
    typedef long long ll;
    
    int n, m;
    int ax, ay, bx, by;
    int g[N][N];
    bool gb[N][N];
    int dx[4] = {0, -1, 0, 1};
    int dy[4] = {-1, 0, 1, 0};
    vector<pair<int, int>> vp;
    bool b = false;
    
    void dfs(int x, int y) {
        if (x == bx && y == by) { // 到达终点
            b = true;
            for (int i = 0; i < vp.size() - 1; i++) {
                cout << '(' << vp[i].first << ',' << vp[i].second << ")->";
            }
            cout << '(' << x << ',' << y << ")" << endl;
            return;
        }
        for (int i = 0; i < 4; i++) { // 四个方向
            int vx = x + dx[i], vy = y + dy[i]; // 走方格
            if (vx >= 1 && vy >= 1 && vx <= n && vy <= m) { // 出界
                if (g[vx][vy] && gb[vx][vy]) { //
                    gb[vx][vy] = false;
                    vp.push_back({vx, vy});
                    dfs(vx, vy);
                    vp.pop_back();
                    gb[vx][vy] = true;
                }
            }
        }
    }
    
    int main() {
        fill(&gb[0][0], &gb[0][0] + N * N, true);
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> g[i][j];
            }
        }
        cin >> ax >> ay;
        cin >> bx >> by;
        gb[ax][ay] = false;
        vp.push_back({ax, ay});
        dfs(ax, ay);
        if (!b) {
            cout << -1 << endl;
        }
        return 0;
    }
    
    

    信息

    ID
    84
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    814
    已通过
    124
    上传者