oj.uz

Submission #975632

# Submission time Handle Problem Language Result Execution time Memory
975632 2024-05-05T15:13:32 Z vjudge1 Awesome Arrowland Adventure (eJOI19_adventure) C++17
0 / 100
 1 ms 436 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char dirs[] = {'E', 'W', 'S', 'N'};

int N, M;
vector<vector<char>> grid;
vector<vector<int>> visited;

bool isValid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < M;
}

int bfs() {
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = 0;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (x == N - 1 && y == M - 1) {
            return visited[x][y];
        }

        int dir = -1;
        for (int i = 0; i < 4; i++) {
            if (grid[x][y] == dirs[i]) {
                dir = i;
                break;
            }
        }

        if (dir == -1) {
            continue;
        }

        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (isValid(nx, ny) && grid[nx][ny] != 'X' && visited[nx][ny] == -1) {
            visited[nx][ny] = visited[x][y];
            q.push({nx, ny});
        } else {
            for (int i = 0; i < 4; i++) {
                if (i != dir) {
                    nx = x + dx[i];
                    ny = y + dy[i];
                    if (isValid(nx, ny) && grid[nx][ny] != 'X' && visited[nx][ny] == -1) {
                        visited[nx][ny] = visited[x][y] + 1;
                        q.push({nx, ny});
                    }
                }
            }
        }
    }

    return -1;
}

int main() {
    cin >> N >> M;
    grid.resize(N, vector<char>(M));
    visited.resize(N, vector<int>(M, -1));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> grid[i][j];
        }
    }

    cout << bfs() << endl;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -