Submission #236070

#TimeUsernameProblemLanguageResultExecution timeMemory
236070kartelPortal (COCI17_portal)C++14
48 / 120
39 ms11768 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-O3") #define F first #define S second #define pb push_back #define N +100500 #define M ll(1e9 + 7) #define sz(x) (int)x.size() #define re return #define oo ll(1e9) #define el '\n' #define pii pair <int, int> using namespace std; //using namespace __gnu_pbds; //typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef long long ll; typedef long double ld; struct step{ int x, y, st; step(int x, int y, int st) : x(x), y(y), st(st) {}; }; queue <step *> q; int mrk[505][505]; char c[505][505]; int Left[505][505], up[505][505], Right[505][505], down[505][505], i, j, n, m, ans, found, x, y, sx, sy, ex, ey; void get(int &x, int &y, int &st) { x = q.front() -> x; y = q.front() -> y; st = q.front() -> st; q.pop(); } void put(int x, int y, int st) { if (x == ex && y == ey) {ans = min(ans, st); return;} q.push(new step(x, y, st)); mrk[x][y] = 1; } void PortalToLeft(int x, int y, int st) { if (Right[x][y] != y + 1 && up[x][y] != x - 1 && down[x][y] != x + 1 && !found) return; int cx = x; int cy = Left[x][y] + 1; if (mrk[cx][cy]) return; put(cx, cy, st + 1); } void PortalToRight(int x, int y, int st) { if (Left[x][y] != y - 1 && up[x][y] != x - 1 && down[x][y] != x + 1) return; int cx = x; int cy = Right[x][y] - 1; if (mrk[cx][cy]) return; put(cx, cy, st + 1); } void PortalToUp(int x, int y, int st) { if (Right[x][y] != y + 1 && Left[x][y] != y - 1 && down[x][y] != x + 1) return; int cx = up[x][y] + 1; int cy = y; // cerr << x << " " << y << " " << cx << " " << cy << el; if (mrk[cx][cy]) return; put(cx, cy, st + 1); } void PortalToDown(int x, int y, int st) { if (Right[x][y] != y + 1 && up[x][y] != x - 1 && Left[x][y] != y - 1) return; int cx = down[x][y] - 1; int cy = y; if (mrk[cx][cy]) return; put(cx, cy, st + 1); } void putall(int x, int y, int st) { int steps[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; for (int i = 0; i < 4; i++) { int cx = x + steps[i][0]; int cy = y + steps[i][1]; if (cx < 1 || cy < 1 || cx > n || cy > m || mrk[cx][cy]) continue; put(cx, cy, st + 1); } if (found) return; PortalToLeft(x, y, st); PortalToRight(x, y, st); PortalToUp(x, y, st); PortalToDown(x, y, st); } int main() { srand(time(0)); ios_base::sync_with_stdio(0); iostream::sync_with_stdio(0); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); //// // in("input.txt"); // out("output.txt"); cin >> n >> m; for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { cin >> c[i][j]; if (c[i][j] == 'C') sx = i, sy = j; if (c[i][j] == 'F') ex = i, ey = j; if (c[i][j] == '#') mrk[i][j] = 1; else mrk[i][j] = 0; } } for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { if (c[i][j] == '#') Left[i][j] = j; else Left[i][j] = Left[i][j - 1]; } for (j = m; j >= 1; j--) { if (c[i][j] == '#') Right[i][j] = j; else Right[i][j] = Right[i][j + 1]; } } for (j = 1; j <= m; j++) { for (i = 1; i <= n; i++) { if (c[i][j] == '#') up[i][j] = i; else up[i][j] = up[i - 1][j]; } for (i = n; i >= 1; i--) { if (c[i][j] == '#') down[i][j] = i; else down[i][j] = down[i + 1][j]; } } ans = oo; put(sx, sy, 0); while (sz(q) && !found) { int st; get(x, y, st); putall(x, y, st); } if (ans == oo) cout << "Nemoguce"; else cout << ans << el; } // //110000 //1100
#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...
#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...