Submission #74889209

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef unsigned __int128 ulll;

void solve() {
    int h,w;
    cin >> h >> w;
    vector<vector<char>> graph(h,vector<char>(w));
    vector<vector<vector<int>>> vis(4,vector<vector<int>>(h,vector<int>(w,0)));
    vector<vector<vector<int>>> trail(4,vector<vector<int>>(h,vector<int>(w)));
    int sti,stj,edi,edj;
    for (int i = 0;i < h;i++) {
        for (int j = 0;j < w;j++) {
            cin >> graph[i][j];
            if (graph[i][j] == 'S') {
                sti = i;
                stj = j;
            } else if (graph[i][j] == 'G') {
                edi = i;
                edj = j;
            }
        }
    }
    queue<tuple<int,int,int,int>> bfs;
    vector<int> di = {1,-1,0,0};
    vector<int> dj = {0,0,1,-1};
    vector<char> dmove = {'D','U','R','L'};
    bfs.push({sti,stj,0,-1});
    bool is = false;
    int edk = -1;
    while (!bfs.empty()) {
        auto &[i,j,cnt,pre] = bfs.front();
        if (i == edi && j == edj) {
            is = true;
            edk = pre;
            break;
        }
        if (cnt >= 5e6) {
            continue;
        }
        for (int k = 0;k < 4;k++) {
            int ii = i + di[k];
            int jj = j + dj[k];
            if (ii < 0 || ii >= h || jj < 0 || jj >= w) {
                continue;
            }
            if (vis[k][ii][jj] == -1) {
                continue;
            }
            if (graph[ii][jj] == '#') {
                continue;
            }
            if (graph[i][j] == 'o') {
                if (dmove[k] != dmove[pre]) {
                    continue;
                }
            }
            if (graph[i][j] == 'x') {
                if (dmove[k] == dmove[pre]) {
                    continue;
                }
            }
            vis[k][ii][jj] = -1;
            trail[k][ii][jj] = pre;
            bfs.push({ii,jj,cnt+1,k});
        }
        bfs.pop();
    }
    if (!is) {
        cout << "No";
    } else {
        cout << "Yes" << '\n';
        string ans = "";
        int cur_i = edi;
        int cur_j = edj;
        int cur_k = edk;
        while(cur_k != -1) {
            ans += dmove[cur_k];
            int prei = cur_i - di[cur_k];
            int prej = cur_j - dj[cur_k];
            int prek = trail[cur_k][cur_i][cur_j];
            cur_i = prei;
            cur_j = prej;
            cur_k = prek;
        }
        reverse(ans.begin(),ans.end());
        cout << ans;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Submission Info

Submission Time
Task D - Go Straight
User t154654
Language C++23 (GCC 15.2.0)
Score 425
Code Size 2718 Byte
Status AC
Exec Time 117 ms
Memory 41864 KiB

Compile Error

./Main.cpp: In function 'solve':
./Main.cpp:36:9: warning: 'edi' may be used uninitialized [-Wmaybe-uninitialized]
   36 |         if (i == edi && j == edj) {
      |         ^
./Main.cpp:14:17: note: 'edi' was declared here
   14 |     int sti,stj,edi,edj;
      |                 ^
./Main.cpp:36:22: warning: 'edj' may be used uninitialized [-Wmaybe-uninitialized]
   36 |         if (i == edi && j == edj) {
      |                      ^
./Main.cpp:14:21: note: 'edj' was declared here
   14 |     int sti,stj,edi,edj;
      |                     ^
./Main.cpp:14:9: warning: 'sti' may be used uninitialized [-Wmaybe-uninitialized]
   14 |     int sti,stj,edi,edj;
      |         ^
./Main.cpp:14:13: warning: 'stj' may be used uninitialized [-Wmaybe-uninitialized]
   14 |     int sti,stj,edi,edj;
      |             ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 3
AC × 46
Set Name Test Cases
Sample example_00.txt, example_01.txt, example_02.txt
All example_00.txt, example_01.txt, example_02.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt
Case Name Status Exec Time Memory
example_00.txt AC 1 ms 3640 KiB
example_01.txt AC 1 ms 3564 KiB
example_02.txt AC 1 ms 3596 KiB
hand_00.txt AC 81 ms 39892 KiB
hand_01.txt AC 20 ms 39912 KiB
hand_02.txt AC 101 ms 41840 KiB
hand_03.txt AC 109 ms 41864 KiB
hand_04.txt AC 1 ms 3540 KiB
hand_05.txt AC 91 ms 39868 KiB
hand_06.txt AC 55 ms 39836 KiB
hand_07.txt AC 93 ms 39892 KiB
hand_08.txt AC 22 ms 40044 KiB
hand_09.txt AC 1 ms 3588 KiB
random_00.txt AC 21 ms 38176 KiB
random_01.txt AC 117 ms 38992 KiB
random_02.txt AC 42 ms 36336 KiB
random_03.txt AC 20 ms 37612 KiB
random_04.txt AC 67 ms 38892 KiB
random_05.txt AC 84 ms 35024 KiB
random_06.txt AC 21 ms 38508 KiB
random_07.txt AC 21 ms 37976 KiB
random_08.txt AC 39 ms 37864 KiB
random_09.txt AC 64 ms 39452 KiB
random_10.txt AC 64 ms 33912 KiB
random_11.txt AC 68 ms 36304 KiB
random_12.txt AC 77 ms 36716 KiB
random_13.txt AC 18 ms 35052 KiB
random_14.txt AC 55 ms 36048 KiB
random_15.txt AC 18 ms 35176 KiB
random_16.txt AC 19 ms 36564 KiB
random_17.txt AC 18 ms 34160 KiB
random_18.txt AC 18 ms 34740 KiB
random_19.txt AC 21 ms 38392 KiB
random_20.txt AC 19 ms 35032 KiB
random_21.txt AC 23 ms 34284 KiB
random_22.txt AC 19 ms 35408 KiB
random_23.txt AC 21 ms 38360 KiB
random_24.txt AC 26 ms 38120 KiB
random_25.txt AC 21 ms 35720 KiB
random_26.txt AC 19 ms 34416 KiB
random_27.txt AC 84 ms 38100 KiB
random_28.txt AC 20 ms 36592 KiB
random_29.txt AC 24 ms 34668 KiB
random_30.txt AC 24 ms 36844 KiB
random_31.txt AC 44 ms 38892 KiB
random_32.txt AC 24 ms 35696 KiB