Submission #950686

#TimeUsernameProblemLanguageResultExecution timeMemory
950686tnknguyen_Patkice (COCI20_patkice)C++14
50 / 50
1 ms748 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define pii pair<int, int> const int sz = 105; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; const int dc[] = {'S', 'N', 'E', 'W'}; int S, T, U, V; char a[sz][sz]; int d[sz][sz]; int n, m; bool valid(int x, int y){ return (x >= 1 && x <= n && y >= 1 && y <= m); } int get(char c){ if(c == '<'){ return 3; } if(c == '>'){ return 2; } if(c == '^'){ return 1; } return 0; } int bfs(int x, int y){ deque<pii> q; memset(d, 63, sizeof d); q.push_front({x, y}); d[x][y] = 0; while(q.size()){ int x, y; tie(x, y) = q.front(); q.pop_front(); if(x == U && y == V){ break; } if(a[x][y] == '.'){ continue; } int i = get(a[x][y]); int u = x + dx[i]; int v = y + dy[i]; if(valid(u, v) && d[x][y] + 1 < d[u][v]){ d[u][v] = d[x][y] + 1; q.push_back({u, v}); } } return d[U][V]; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("main.inp","r",stdin); // freopen("main.out","w",stdout); cin>>n>>m; for(int i=1; i<=n; ++i){ for(int j=1; j<=m; ++j){ cin>>a[i][j]; if(a[i][j] == 'o'){ S = i; T = j; } if(a[i][j] == 'x'){ U = i; V = j; } } } vector<pair<int, char>> ans; for(int i=0; i<4; ++i){ int u = S + dx[i]; int v = T + dy[i]; if(valid(u, v)){ int t = bfs(u, v); ans.push_back({t, dc[i]}); } } sort(ans.begin(), ans.end()); if(ans[0].first != d[0][0]){ cout<<":)"<<endl<<ans[0].second; } else{ cout<<":("; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...