//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
typedef pair<int, int> T;
const int oo = 1e9+7;
const int mx = 2500;
void solve(){
int n, m, k;
T s, e;
scanf("%d %d %d %d %d %d %d", &n, &m, &k, &s.first, &s.second, &e.first, &e.second);
vector a(n+1, vector<char>(m+1));
for (int i = 1; i<=n; i++){
for (int j = 1; j<=m; j++){
scanf("%c", &a[i][j]);
}
}
auto in = [&](T ss){
return ss.first >= 1 && ss.second >= 1 && ss.first <= n && ss.second <= m;
};
queue<T>q, q2;
vector<bitset<mx>>tab(m+1);
for (int j = 1; j<=m; j++){
for (int i = 1; i<=n; i++){
tab[j].set(i);
}
}
vector<int>X = {-1, 1, 0, 0};
vector<int>Y = {0, 0, -1, 1};
vector dist(n+1, vector<int>(m+1, oo));
dist[s.first][s.second] = 0;
q.push(s);
tab[s.second].set(s.first, 0);
while (dist[e.first][e.second] == oo){
while ((int)q.size()){
auto v = q.front(); q.pop();
for (int ck = 0; ck < 4; ck++){
T x = {v.first + X[ck], v.second + Y[ck]};
if (!in(x)) continue;
if (a[x.first][x.second] == '.'){
if (dist[x.first][x.second] == oo){
dist[x.first][x.second] = dist[v.first][v.second];
tab[x.second].set(x.first, 0);
q.push(x);
}
}
}
q2.push(v);
}
auto v = q2.front(); q2.pop();
for (int i = max(1, v.second - k); i<=min(m, v.second+k); i++){
int from = (i == v.second - k || i == v.second + k ? max(1, v.first-k+1) : max(1, v.first-k));
int to = (i == v.second - k || i == v.second + k ? min(n, v.first+k-1) : min(n, v.first+k));
for (int now = tab[i]._Find_next(from-1); now <= to; now = tab[i]._Find_next(now)){
dist[now][i] = dist[v.first][v.second]+1;
tab[i].set(now, 0);
q.push({now, i});
}
}
}
// for (int i = 1; i<=n; i++){
// for (int j = 1; j<=m; j++){
// cerr << dist[i][j] << " ";
// }
// cerr << "\n";
// }
printf("%d\n", dist[e.first][e.second]);
}
int32_t main(){
int t = 1;
//cin >> t;
while (t--) solve();
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf("%d %d %d %d %d %d %d", &n, &m, &k, &s.first, &s.second, &e.first, &e.second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:38:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%c", &a[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
