Submission #1211714

#TimeUsernameProblemLanguageResultExecution timeMemory
1211714mehraliiAwesome Arrowland Adventure (eJOI19_adventure)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template <typename T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define ll long long #define pb push_back #define ppb pop_back #define pf push_front #define ppf pop_front #define eb emplace_back #define F fist #define S second constexpr int MAXN = 1e5; const int LOG = __lg(MAXN)+1; constexpr int INF = 1e9; constexpr int MOD = 1e9+7; constexpr double EPS = 1e-8; /* EJOI 2019, Day 2, problem A, 12p. */ int f(char f, char t){ if (f == t){ return 0; } if (f == 'W'){ if (t == 'N'){ return 1; } else if (t == 'E'){ return 2; } else { return 3; } } else if (f == 'N'){ if (t == 'W'){ return 3; } else if (t == 'S'){ return 2; } else { return 1; } } else if (f == 'E'){ if(t == 'W'){ return 2; } else if (t == 'S'){ return 1; } else { return 3; } } else{ if (t == 'W'){ return 1; } else if (t == 'N'){ return 2; } else { return 3; } } } int n, m; vector<string> grid; vector<vector<bool>> vis; int solve(int x, int y){ if (x == n-1 && y == m-1){ return 0; } if (grid[x][y] == 'X'){ return INF; } vis[x][y] = true; static vector<int> dx = {1, -1, 0, 0}; static vector<int> dy = {0, 0, -1, 1}; static string v = "SNWE"; int res = INF; for (int k = 0; k < 4; k++){ int tx = x + dx[k], ty = y + dy[k]; if(0 <= tx && tx < n && 0 <= ty && ty < m && !vis[tx][ty]){ res = min(res, f(grid[x][y], v[k]) + solve(tx, ty)); } } vis[x][y] = false; return res; } void solve(){ cin >> n >> m; grid.resize(n); vis.assign(n, vector<bool>(m, 0)); for(auto& x: grid){ cin >> x; } cout << solve(0, 0) << '\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; for(int i = 1; i <= t; i++){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...