Submission #823839

#	Time	Username	Problem	Language	Result	Execution time	Memory
823839		thimote75	Maze (JOI23_ho_t3)	C++14	100 / 100	438 ms	53104 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;
using bdata = vector<bool>;
using bgrid = vector<bdata>;

using point = pair<int, int>;

int N, M, B;
igrid visited;
bgrid isTransparent;

vector<point> adjacent (point source, bool diagonal) {
    if (diagonal) {
        return {
            { source.first - 1, source.second - 1 },
            { source.first + 1, source.second - 1 },
            { source.first - 1, source.second + 1 },
            { source.first + 1, source.second + 1 },
            { source.first,     source.second - 1 },
            { source.first,     source.second + 1 },
            { source.first - 1, source.second     },
            { source.first + 1, source.second     }
        };
    }

    return {
        { source.first,     source.second - 1 },
        { source.first,     source.second + 1 },
        { source.first - 1, source.second     },
        { source.first + 1, source.second     }
    };
}

int bfs (point source, point target) {
    deque<point> bfs_queue;
    visited[source.first][source.second] = 0;

    bfs_queue.push_front(source);

    while (bfs_queue.size() != 0) {
        point current = bfs_queue.front();
        bfs_queue.pop_front();

        bool isDiagonal = visited[current.first][current.second] % B != 0;

        for (point next : adjacent(current, isDiagonal)) {
            if (next.first  < 0 || next.first  >= N) continue ;
            if (next.second < 0 || next.second >= M) continue ;

            if (visited[next.first][next.second] != -1) continue ;

            bool plus = isDiagonal || (!isTransparent[next.first][next.second]);
            
            if (plus) {
                visited[next.first][next.second] = visited[current.first][current.second] + 1;
                bfs_queue.push_back(next);
            } else {
                visited[next.first][next.second] = visited[current.first][current.second];
                bfs_queue.push_front(next);
            }
        }
    }

    double a = visited[target.first][target.second];
    double b = B;

    return (int) ceil(a / b);
}

int main () {
    cin >> N >> M >> B;
    visited.resize(N, idata(M, - 1));

    int sx, sy;
    cin >> sx >> sy;
    sx --; sy --;
    int tx, ty;
    cin >> tx >> ty;
    tx --; ty --;

    isTransparent.resize(N, bdata(M));

    for (int i = 0; i < N; i ++) {
        string buffer;
        cin >> buffer;

        for (int j = 0; j < M; j ++)
            isTransparent[i][j] = buffer[j] == '.';
    }

    cout << bfs({ sx, sy }, { tx, ty }) << "\n";
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6