Submission #382000

#TimeUsernameProblemLanguageResultExecution timeMemory
382000AraragiPatkice II (COCI21_patkice2)C++17
55 / 110
1613 ms81496 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("00") typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int, int> pii; ll time() {return chrono::system_clock().now().time_since_epoch().count();} mt19937 rnd(time()); const int inf = 1e9; const ll inf64 = 1e18; #define ft first #define fin(x) ifstream cin("x.in"); #define fout(x) ofstream cout("x.out"); #define sd second #define pb push_back #define sz(x) (int)x.size() char grid[2001][2001]; int dst[2001][2001]; bool was[2001][2001]; array<int, 3> mem[2001][2001]; int steps[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; void solve() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) dst[i][j] = inf; int sx = 0, sy = 0, ex = 0, ey = 0; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { cin >> grid[i][j]; if (grid[i][j] == 'o') { sx = i; sy = j; } else if (grid[i][j] == 'x') { ex = i; ey = j; } } priority_queue< pair< pair<int, int>, int > > q; q.push({{0, sx}, sy}); was[sx][sy] = true; dst[sx][sy] = 0; while (!q.empty()) { int cost = -q.top().ft.ft; int fx = q.top().ft.sd; int fy = q.top().sd; q.pop(); if (cost > dst[fx][fy]) continue; was[fx][fy] = true; for (int i = 0; i < 4; i++) { int cx = fx + steps[i][0]; int cy = fy + steps[i][1]; int pay = 1; if (fx == sx && fy == sy) pay = 0; if (steps[i][0] == 1 && grid[fx][fy] == 'v') pay = 0; if (steps[i][0] == -1 && grid[fx][fy] == '^') pay = 0; if (steps[i][1] == 1 && grid[fx][fy] == '>') pay = 0; if (steps[i][1] == -1 && grid[fx][fy] == '<') pay = 0; if (!(cx >= 0 && cx < n && cy >= 0 && cy < m && !was[cx][cy])) continue; if (cost + pay < dst[cx][cy]) { dst[cx][cy] = cost + pay; q.push({{-(cost + pay), cx}, cy}); mem[cx][cy] = {fx, fy, i}; } } } // vector< array<int, 3> > path; // int x = ex, y = ey; // int type = mem[ex][ey][0]; // while (x != sx && y != sy) // { // if (x != ex || y != ey) // path.pb({x, y, type}); // auto nx = mem[x][y]; // x = nx[0]; // y = nx[1]; // type = nx[2]; // } //path.pb({sx, sy, -1}); //reverse(path.begin(), path.end()); // for (auto it : path) // cout << it[0] + 1 << " " << it[1] + 1 << " " << it[2] << '\n'; //for (auto it : path) // { // if (it[2] == 0) // grid[it[0]][it[1]] = 'v'; // else if (it[2] == 1) // grid[it[0]][it[1]] = '^'; // else if (it[2] == 2) // grid[it[0]][it[1]] = '>'; // else if (it[2] == 3) // grid[it[0]][it[1]] = '<'; // } cout << dst[ex][ey] << '\n'; for (int i = 0; i < n; i++, cout << '\n') for (int j = 0; j < m; j++) cout << grid[i][j]; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef _LOCAL_ system("color 2"); #endif // _LOCAL_ int t = 1; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...