| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 914135 |
2024-01-21T09:14:11 Z |
mychecksedad |
Maze (JOI23_ho_t3) |
C++17 |
|
2000 ms |
179284 KB |
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 6e6+100, M = 1e5+10, K = 52, MX = 30;
int r, c, n, sx, sy, ex, ey, arr[4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
string s[5000];
vector<vector<int>> dp;
void solve(){
cin >> r >> c >> n >> sx >> sy >> ex >> ey;
sx--, sy--, ex--, ey--;
for(int i = 0; i < r; ++i) cin >> s[i];
vector<vector<pair<int, int>>> C;
vector<vector<int>> vis(r, vector<int>(c));
vector<vector<array<int, 2>>> dist(r, vector<array<int, 2>>(c));
vector<vector<int>> dp(r, vector<int>(c, MOD));
for(int i = 0; i < r; ++i){
for(int j = 0; j < c; ++j){
if(s[i][j] == '#' || vis[i][j]) continue;
queue<pair<int, int>> q;
q.push({i, j});
vis[i][j] = C.size() + 1;
C.pb({});
while(!q.empty()){
int x = q.front().first, y = q.front().second;
q.pop();
C.back().pb({x, y});
for(int l = 0; l < 4; ++l){
int x1 = x + arr[l][0], x2 = y + arr[l][1];
if(x1 >= 0 && x2 >= 0 && x1 < r && x2 < c && s[x1][x2] != '#' && !vis[x1][x2]){
q.push({x1, x2});
vis[x1][x2] = C.size();
}
}
}
}
}
auto comp = [&](const array<int, 2> &x, const array<int, 2> &y){
return max(abs(dist[x[0]][x[1]][0]), abs(dist[x[0]][x[1]][1])) > max(abs(dist[y[0]][y[1]][0]), abs(dist[y[0]][y[1]][1]));
};
priority_queue<array<int, 2>, vector<array<int, 2>>, decltype(comp)> Q(comp);
for(auto p: C[vis[sx][sy] - 1]){
int x = 0, req = 4;
for(int l = 0; l < 4; ++l){
int a = arr[l][0] + p.first, b = arr[l][1] + p.second;
if(a >= 0 && b >= 0 && a < r && b < c){
if(vis[a][b] == vis[p.first][p.second]) ++x;
}else --req;
}
dp[p.first][p.second] = 0;
dist[p.first][p.second] = {0};
if(x < req) Q.push({p.first, p.second});
}
int cur = 0;
while(dp[ex][ey] == MOD){
vector<pair<int, int>> Sn;
while(!Q.empty()){
int x = Q.top()[0], y = Q.top()[1]; Q.pop();
// cout << x << ' '<< y << ' ' << cur << ' ' << dist[x][y][0] << ' ' << dist[x][y][1] << endl;
int curx = dist[x][y][0], cury = dist[x][y][1];
for(int l = 0; l < 4; ++l){
int a = x + arr[l][0], b = y + arr[l][1];
if(a >= 0 && b >= 0 && a < r && b < c){
if(max(abs(curx + arr[l][0]), abs(cury + arr[l][1])) > n || abs(curx + arr[l][0]) + abs(cury + arr[l][1]) == 2*n){
if(dp[a][b] == MOD && vis[a][b] > 0){
for(auto p: C[vis[a][b] - 1]){
dp[p.first][p.second] = cur + 1;
Sn.pb(p);
}
}
continue;
}
dp[a][b] = cur + 1;
dist[a][b] = {curx + arr[l][0], cury + arr[l][1]};
Sn.pb({a, b});
Q.push({a, b});
}
}
}
for(auto p: Sn){
int x = 0, req = 4;
for(int l = 0; l < 4; ++l){
int a = arr[l][0] + p.first, b = arr[l][1] + p.second;
if(a >= 0 && b >= 0 && a < r && b < c){
if(dp[a][b] < MOD) ++x;
}else --req;
}
if(x < req){
Q.push({p.first, p.second});
dist[p.first][p.second] = {0};
}
}
++cur;
}
// for(int i = 0; i < r; ++i){
// for(int j = 0 ;j < c; ++j) cout << dp[i][j] << ' ';
// en;
// }
cout << dp[ex][ey];
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:117:15: warning: unused variable 'aa' [-Wunused-variable]
117 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2032 ms |
157032 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
179284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2012 ms |
178020 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
179284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
179284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2032 ms |
157032 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2032 ms |
157032 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2032 ms |
157032 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
