Submission #1259367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259367		arnob_chowdhury	Knapsack (NOI18_knapsack)	C++20	0 / 100	5 ms	12868 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int pos, len, dir;
};

int n, m, s, e;
vector<char> grid;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int dis[200005][4][4];
queue<Node> q;

int to(int i, int j) { return (i - 1) * m + j; }

int bfs() {
    for (int d = 0; d < 4; ++d) {
        q.push({s, 1, d});
        dis[s][1][d] = 0;
    }

    while (!q.empty()) {
        Node u = q.front(); q.pop();
        if (u.pos == e) return dis[e][u.len][u.dir];

        for (int i = 0; i < 4; ++i) {
            Node v = u;
            v.pos += dx[i] * m + dy[i];
            v.len = (u.dir == i) ? u.len + 1 : 1;
            v.dir = i;

            if (v.pos < 1 || v.pos > n * m || v.len > 3) continue;
            if (dis[v.pos][v.len][v.dir] != 0x3f3f3f3f) continue;
            if (grid[v.pos] == '#') continue;

            dis[v.pos][v.len][v.dir] = dis[u.pos][u.len][u.dir] + 1;
            q.push(v);
        }
    }
    return -1;
}

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

    memset(dis, 0x3f, sizeof dis);
    cin >> n >> m;
    grid.resize(n * m + 1);

    for (int i = 1; i <= n * m; ++i) {
        cin >> grid[i];
        if (grid[i] == 'S') s = i;
        if (grid[i] == 'T') e = i;
    }

    cout << bfs();
    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27