제출 #1121806

#제출 시각아이디문제언어결과실행 시간메모리
1121806stefanneaguMaze (JOI23_ho_t3)C++17
8 / 100
125 ms25408 KiB
#include <bits/stdc++.h> using namespace std; struct state { int a, b, si, sj, ji, jj; }; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, -1, 1}; vector<vector<bool>> v, f; vector<vector<int>> dp; bool in(int a, int b, int x, int y, int i, int j) { if(v[i][j] == 1) { return 1; } if(i == a && j == b) { return 0; } if(i == x && j == y) { return 0; } if(i == a && j == y) { return 0; } if(i == x && j == b) { return 0; } if(a <= i && i <= x && b <= j && j <= y) { return 1; } return 0; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(); cout.tie(); int n, m, d; cin >> n >> m >> d; v.resize(n + 2, vector<bool>(m + 2)); f.resize(n + 2, vector<bool>(m + 2)); dp.resize(n + 2, vector<int>(m + 2)); int s1, s2, e1, e2; cin >> s1 >> s2 >> e1 >> e2; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { char ch; cin >> ch; if(ch == '.') { ch = 1; } else { ch = 0; } v[i][j] = ch; dp[i][j] = 1e9; } } dp[s1][s2] = 0; deque<state> dq; dq.push_front({s1, s2, -1, -1, -1, -1}); int val = 0, i, j; while(!dq.empty()) { auto [a, b, si, sj, ji, jj] = dq.front(); dq.pop_front(); if(f[a][b]) { continue; } f[a][b] = 1; for(int dd = 0; dd < 4; dd++) { i = a + dx[dd]; j = b + dy[dd]; if(min(i, j) < 1 || i > n || j > m) { continue; } val = 1 - in(si, sj, ji, jj, i, j); if(dp[a][b] + val < dp[i][j]) { if(!val) { dp[i][j] = dp[a][b]; dq.push_front({i, j, si, sj, ji, jj}); } else { dp[i][j] = dp[a][b] + 1; dq.push_back({i, j, a - d, b - d, a + d, b + d}); } } } } cout << dp[e1][e2]; 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...