Submission #899411

#TimeUsernameProblemLanguageResultExecution timeMemory
899411LiuBruhMaze (JOI23_ho_t3)C++17
0 / 100
1 ms600 KiB
#include <bits/stdc++.h> #define int long long #define F first #define S second #define sz(v) (int)v.size() using namespace std; const int INF = (int)1e18 + 5; const int dx[4] = {0, 0, 1, -1}; const int dy[4] = {1, -1, 0, 0}; int r, c, n; int sx, sy, tx, ty; vector<vector<int>> g, dis, vis; vector<vector<vector<int>>> e; bool out(int x, int y) { return min(x, y) < 1 or x > r or y > c; } void solve() { cin >> r >> c >> n >> sx >> sy >> tx >> ty; g = vector<vector<int>> (r + 1, vector<int> (c + 1)); e = vector<vector<vector<int>>> (r + 1, vector<vector<int>> (c + 1, vector<int> (4))); dis = vector<vector<int>> (r + 1, vector<int> (c + 1)); vis = vector<vector<int>> (r + 1, vector<int> (c + 1)); for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) { char ch; cin >> ch; g[i][j] = (ch == '.'); } } for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) { int nx, ny; for (int k = 0; k < 4; k++) { nx = i + dx[k]; ny = j + dy[k]; if (!out(nx, ny)) { e[i][j][k] = (g[nx][ny] == 0); } } } } deque<pair<pair<int, int>, int>> dq; dq.push_back({{sx, sy}, 0}); vis[sx][sy] = true; while (!dq.empty()) { auto [coo, d] = dq.front(); dq.pop_front(); auto [x, y] = coo; dis[x][y] = d; int nx, ny; for (int k = 0; k < 4; k++) { nx = x + dx[k], ny = y + dy[k]; if (out(nx, ny) or vis[nx][ny]) continue; vis[nx][ny] = true; if (e[x][y][k] == 0) { dq.push_front({{nx, ny}, d}); } else { dq.push_front({{nx, ny}, d + 1}); } } } cout << dis[r][c] << '\n'; } signed main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); solve(); return 0; }
#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...