| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1080540 |
2024-08-29T10:50:26 Z |
TAhmed33 |
Maze (JOI23_ho_t3) |
C++ |
|
1 ms |
348 KB |
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long ll;
const int inf = 1e9;
int n, m, K;
pair <int, int> s, g;
vector <vector <char>> a;
vector <vector <bool>> vis;
vector <vector <int>> dist;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
bool valid (int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m && !vis[x][y];
}
void solve () {
cin >> n >> m >> K;
cin >> s.first >> s.second;
cin >> g.first >> g.second;
s.first--; s.second--; g.first--; g.second--;
a.resize(n, vector <char> (m));
vis.resize(n, vector <bool> (m, false));
dist.resize(n, vector <int> (m, inf));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
vis[i][j] = 0;
}
}
vis[s.first][s.second] = 1;
dist[s.first][s.second] = 0;
deque <pair <int, int>> cur;
cur.push_back(s);
int rem = n * m - 1;
int ss = 0;
while (rem > 0) {
/* cout << rem << '\n';
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << vis[i][j];
}
cout << '\n';
}
cout << '\n';*/
if (cur.empty()) {
break;
}
deque <array <int, 4>> dd;
while (!cur.empty()) {
auto k = cur.front();
cur.pop_front();
//cout << k.first << " " << k.second << '\n';
bool flag = 0;
for (int i = 0; i < 4; i++) {
int x = k.first + dx[i];
int y = k.second + dy[i];
if (!valid(x, y)) {
continue;
}
if (a[x][y] == '.') {
dist[x][y] = ss;
vis[x][y] = 1;
cur.push_back({x, y});
rem--;
} else {
flag = 1;
}
}
if (flag) {
dd.push_back({k.first, k.second, 0, 0});
}
}
ss++;
while (!dd.empty()) {
auto k = dd.front();
dd.pop_front();
bool flag = 0;
for (int i = 0; i < 4; i++) {
array <int, 4> g = {k[0] + dx[i], k[1] + dy[i], k[2] + abs(dx[i]), k[3] + abs(dy[i])};
/* for (auto j : k) cout << j << " ";
cout << '\n';
cout << ": \n";
for (auto k : g) {
cout << k << " ";
}
cout << '\n' << '\n';*/
if (valid(g[0], g[1]) && g[2] <= K && g[3] <= K && g[2] + g[3] < 2 * K) {
vis[g[0]][g[1]] = 1;
dist[g[0]][g[1]] = ss;
dd.push_back(g);
rem--;
}
}
if (!flag) {
cur.push_back({k[0], k[1]});
}
}
}
cout << dist[g.first][g.second] << '\n';
}
signed main () {
#ifndef ONLINE_JUDGE
freopen("input_file", "r", stdin);
//freopen("output_file", "w", stdout);
#endif
//ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:103:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | freopen("input_file", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
