#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int r, c, N;
cin >> r >> c >> N;
int sti, stj, eni, enj;
cin >> sti >> stj >> eni >> enj;
sti -= 1;
stj -= 1;
eni -= 1;
enj -= 1;
vector<vector<char>> a(r, vector<char>(c));
for (int i =0 ; i < r; ++i) {
for (int j =0 ; j < c; ++j) {
cin >> a[i][j];
}
}
vector<vector<int>> dist(r, vector<int>(c, r * c + 1));
dist[sti][stj] = 0;
deque<array<int, 2>> dq;
dq.push_front({sti, stj});
vector<int> dx = {0, 1, -1, 0}, dy = {1, 0, 0, -1};
while (dq.size()) {
int i = dq.front()[0];
int j = dq.front()[1];
dq.pop_front();
for (int k = 0; k < 4; ++k) {
int ni = i + dx[k];
int nj = j + dy[k];
if (ni < 0 || nj < 0 || ni >= r || nj >= c) continue;
int add = (a[ni][nj] == '#');
if (dist[ni][nj] > dist[i][j] + add) {
dist[ni][nj] = dist[i][j] + add;
if (add) dq.push_back({ni, nj});
else dq.push_front({ni, nj});
}
}
}
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
//~ cout << dist[i][j] << " ";
}
//~ cout << "\n";
}
cout << dist[eni][enj] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |