Submission #1101255

#TimeUsernameProblemLanguageResultExecution timeMemory
1101255huantranPatkice (COCI20_patkice)C++17
30 / 50
1 ms512 KiB
#include <iostream> #include <algorithm> #include <cstring> #include <string.h> #include <vector> #include <math.h> #include <map> #include <set> #include <queue> #include <iomanip> #include <numeric> #include <random> #include <chrono> #include <fstream> #include <stack> #include <cmath> #define bit(x, i) (((x) >> (i)) & 1LL) #define rand rd #define PI acos(-1) using namespace std; typedef long long int ll; const int maxn = 1e2 + 5; const ll mod = 998244353; const int inf = 1e9; const ll base = 1e5 + 7; using pll = pair<ll, ll>; const string NAME = "LOCO"; const int NTEST = 100; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); ll Rand(ll l, ll r) { return l + rd() % (r - l + 1); } int n, m, s, t, x, y; char adj[maxn][maxn]; map<char, pair<int, int>> dir; map<int, char> conv, conv_2; int dis[maxn][maxn]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> adj[i][j]; if (adj[i][j] == 'o') s = i, t = j; if (adj[i][j] == 'x') x = i, y = j; } } set<pair<int, int>> ans; conv[0] = 'N', conv[1] = 'E', conv[2] = 'W', conv[3] = 'S'; conv_2['^'] = 0, conv_2['>'] = 1, conv_2['<'] = 2, conv_2['v'] = 3; dir['N'] = {-1, 0}, dir['E'] = {0, 1}, dir['W'] = {0, -1}, dir['S'] = {1, 0}; for (int k = 0; k < 4; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dis[i][j] = inf; } } queue<pair<int, int>> q; int u = s + dir[conv[k]].first, v = t + dir[conv[k]].second; dis[s][t] = 0; if (u >= 1 && u <= n && t >= 1 && t <= m && adj[u][v] != '.') q.push({u, v}), dis[u][v] = 1; while (!q.empty()) { int u = q.front().first; int v = q.front().second; // if (k == 3) // cout << "Go: " << u << ' ' << v << '\n'; q.pop(); int u_x = u + dir[conv[conv_2[adj[u][v]]]].first; int v_x = v + dir[conv[conv_2[adj[u][v]]]].second; if (u_x >= 1 && u_x <= n && v_x >= 1 && v_x <= m && adj[u_x][v_x] != '.' && dis[u_x][v_x] > dis[u][v] + 1) q.push({u_x, v_x}), dis[u_x][v_x] = dis[u][v] + 1; } if (dis[x][y] != inf) ans.insert({dis[x][y], k}); } if (ans.size()) { cout << ":)" << '\n'; cout << conv[(*ans.begin()).second]; } else cout << ":("; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...