Created
March 10, 2019 08:52
-
-
Save donjar/0507b90874c15161eecba8c01063195c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define PI acos(-1.0) | |
| #define MOD 1000000007 | |
| template<class T1, class T2> | |
| using umap = unordered_map<T1, T2>; | |
| template<class T> | |
| using uset = unordered_set<T>; | |
| typedef long long ll; | |
| typedef unsigned long long ull; | |
| typedef long double ld; | |
| typedef pair<int, int> ii; | |
| typedef tuple<int, int, int> iii; | |
| inline int gid(int x, int y) { | |
| return (x + 202) * 202 + y + 202; | |
| } | |
| int main() { | |
| ios::sync_with_stdio(false); | |
| cin.tie(nullptr); | |
| cout.tie(nullptr); | |
| int n; | |
| cin >> n; | |
| for (int i = 0; i < n; ++i) { | |
| umap<int, uset<int>> al; | |
| int k; | |
| cin >> k; | |
| int x = 0; | |
| int y = 0; | |
| for (int j = 0; j < k; ++j) { | |
| char c; | |
| cin >> c; | |
| int g = gid(x, y); | |
| if (c == 'N') { | |
| al[g].insert(gid(x, y + 1)); | |
| al[gid(x, y + 1)].insert(g); | |
| ++y; | |
| } else if (c == 'S') { | |
| al[g].insert(gid(x, y - 1)); | |
| al[gid(x, y - 1)].insert(g); | |
| --y; | |
| } else if (c == 'E') { | |
| al[g].insert(gid(x + 1, y)); | |
| al[gid(x + 1, y)].insert(g); | |
| ++x; | |
| } else { | |
| al[g].insert(gid(x - 1, y)); | |
| al[gid(x - 1, y)].insert(g); | |
| --x; | |
| } | |
| } | |
| queue<pair<int, int>> bfs; | |
| uset<int> visited; | |
| bfs.emplace(gid(0, 0), 0); | |
| int t = gid(x, y); | |
| while (true) { | |
| auto ne = bfs.front(); | |
| if (ne.first == t) { | |
| cout << ne.second << endl; | |
| break; | |
| } | |
| if (visited.count(ne.first) > 0) { | |
| continue; | |
| } | |
| bfs.pop(); | |
| visited.insert(ne.first); | |
| for (auto nei : al[ne.first]) { | |
| if (visited.count(nei) > 0) continue; | |
| bfs.emplace(nei, ne.second + 1); | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment