Submission #1195878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195878		sheina906	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	12 / 100	1 ms	528 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second



unordered_map<char, unordered_map<char, int>> cost;

bool pos(vector<string> &v)
{
    pair<int, int> p = {0, 0};
    for (int i = 0; i < 20 && p.f >= 0 && p.f < 3 && p.s >= 0 && p.s < 3; i++)
    {
        if (v[p.f][p.s] == 'N') p.f--;
        else if (v[p.f][p.s] == 'S') p.f++;
        else if (v[p.f][p.s] == 'W') p.s--;
        else if (v[p.f][p.s] == 'E') p.s++;
    }
    return p.f == 2 && p.s == 2;
}

int bck(int i, int j, vector<string> &v, int tmp)
{
    if (i == 2 && j == 2) return pos(v) ? tmp : 100;
    char t = v[i][j];
    int Nj = (j+1) % 3;
    int Ni = i + !Nj;
    int m = 100;

    if (t == 'X') return bck(Ni, Nj, v, tmp);

    v[i][j] = 'W';
    m = min(m, bck(Ni, Nj, v, tmp + cost[t]['W']));

    v[i][j] = 'N';
    m = min(m, bck(Ni, Nj, v, tmp + cost[t]['N']));

    v[i][j] = 'S';
    m = min(m, bck(Ni, Nj, v, tmp + cost[t]['S']));

    v[i][j] = 'E';
    m = min(m, bck(Ni, Nj, v, tmp + cost[t]['E']));

    v[i][j] = t;


    return m;
}


int main()
{
    cost['N']['N'] = cost['E']['E'] = cost['S']['S'] = cost['W']['W'] = 0;
    cost['N']['E'] = cost['E']['S'] = cost['S']['W'] = cost['W']['N'] = 1;
    cost['N']['S'] = cost['E']['W'] = cost['S']['N'] = cost['W']['E'] = 2;
    cost['N']['W'] = cost['E']['N'] = cost['S']['E'] = cost['W']['S'] = 3;


    int n, m; cin >> n >> m;
    vector<string> v(n);
    for (string &s : v) cin >> s;

    int ans = bck(0, 0, v, 0);
    cout << (ans == 100 ? -1 : ans) << '\n';
    


    return 0;
}


// int main()
// {
//     int n, m, k; cin >> n >> m;
//     vector<string> g(n);
//     for (string &s : g) cin >> s;
//     vector<vector<vector<int>>> dp(n, vector<vector<int>> (m, vector<int> (k)));

// }

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 12 / 12
• Subtask 4: 0 / 16
• Subtask 5: 0 / 50