Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast,no-stack-protector")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
- #pragma GCC optimize("unroll-loops", "fast-math")
- #include <iostream>
- #include <algorithm>
- #include <fstream>
- #include <vector>
- #include <queue>
- #include <functional>
- #include <set>
- #include <map>
- #include <math.h>
- #include <cmath>
- #include <string>
- #include <random>
- #include <unordered_set>
- #include <unordered_map>
- #include <bitset>
- #include <string.h>
- #include <stack>
- #include <assert.h>
- #include <list>
- using namespace std;
- //
- #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
- #define cin in
- #define cout out
- #define ll long long
- #define db double
- #define ld long double
- #define uset unordered_set
- #define umap unordered_map
- #define F first
- #define S second
- #define ms multiset
- #define pb push_back
- #define pq priority_queue
- #define umap unordered_map
- #define uset unordered_set
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define pdd pair<ld, ld>
- #define pnn pair<Node*, Node*>
- #define uid uniform_int_distribution
- #define PI acos(-1.0)
- ifstream in("input.txt");
- ofstream out("output.txt");
- const int MAX_N = 1000, MAX_V = MAX_N * MAX_N;
- vector<int> tg[MAX_V];
- int g[MAX_V], act[MAX_V], add[MAX_V];
- bool bot[MAX_V], used[MAX_V];
- int n, m, G;
- int pos(int i, int j) {
- return i * m + j;
- }
- void input() {
- cin >> n >> m >> G;
- for (int i = 0; i < n; i++) {
- string s;
- cin >> s;
- for (int j = 0; j < m; j++) {
- int v = pos(i, j);
- if (s[j] == 'N' || s[j] == 'n')
- g[v] = (pos(i - 1, j));
- else if (s[j] == 'E' || s[j] == 'e')
- g[v] = (pos(i, j + 1));
- else if (s[j] == 'S' || s[j] == 's')
- g[v] = (pos(i + 1, j));
- else
- g[v] = (pos(i, j - 1));
- if (s[j] == 'N' || s[j] == 'E' || s[j] == 'S' || s[j] == 'W')
- bot[v] = 1;
- }
- }
- n *= m;
- for (int v = 0; v < n; v++)
- tg[g[v]].push_back(v);
- }
- bool cur_used[MAX_V];
- void find_cyc(int v, vector<int>& cyc) {
- stack<int> st;
- while (!cur_used[v]) {
- st.push(v);
- cur_used[v] = 1;
- v = g[v];
- }
- cyc.push_back(v);
- while (st.top() != v) {
- cyc.push_back(st.top());
- st.pop();
- }
- reverse(cyc.begin(), cyc.end());
- }
- int ans = 0;
- int T = 0;
- struct tr {
- int k, t, v;
- };
- /*
- хочу знать минимальное время, для которого можно выстроить
- не более K роботов в "очередь" на выход из поддерева
- и время, в которое их нужно активировать
- */
- tr q(int v, int K) {
- }
- void solve(int v) {
- vector<int> cyc;
- find_cyc(v, cyc);
- int bot_cyc = 0;
- {
- bool fl = 0;
- for (int x : cyc) {
- if (bot[x]) {
- act[x] = T;
- fl = 1;
- bot_cyc++;
- }
- else if (fl)
- T++;
- }
- }
- int k = cyc.size() - bot_cyc;
- }
- int main() {
- fast;
- input();
- memset(act, 255, sizeof(act));
- for (int v = 0; v < n; v++) {
- if(!used[v])
- solve(v);
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement