-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathabc246_e.cpp
More file actions
56 lines (53 loc) · 1.31 KB
/
abc246_e.cpp
File metadata and controls
56 lines (53 loc) · 1.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
typedef long long ll;
using namespace std;
struct Node {
int x, y,c;
};
struct Compare {
bool operator()(const Node& m1, const Node& m2) {
return m1.c > m2.c;
}
};
void solve(){
int N; cin >> N;
int ax,ay; cin >> ax>>ay;
int bx,by; cin >> bx>>by;
ax--,ay--,bx--,by--;
string map[N]; for (int i = 0; i<N;i++) cin >> map[i];
bool visited[N][N]; memset(visited,0,sizeof(visited));
int counts[N][N]; memset(counts,-1,sizeof(counts));
priority_queue<Node,vector<Node>,Compare> q; q.push({ax,ay,0});
while(q.size()) {
auto [x,y,count] = q.top(); q.pop();
if (x == bx && y == by) {
cout << count << endl;
return;
}
int xxxx[]= {-1,-1,1,1};
int yyyy[]= {-1,1,1,-1};
int nc = count+1;
for (int i = 0; i < 4; i++) {
int nx = x+xxxx[i];
int ny = y+yyyy[i];
while (nx >=0 && ny >=0 && nx < N && ny < N && map[nx][ny] == '.') {
if ((!visited[nx][ny]) && (counts[nx][ny] == -1 || counts[nx][ny] > nc)) {
visited[nx][ny] = true;
counts[nx][ny]=nc;
q.push({nx,ny,nc});
}
nx += xxxx[i];
ny += yyyy[i];
}
}
}
cout << -1;
}
int main(){
cout.tie(0);cin.tie(0)->sync_with_stdio(0);
solve();
return 0;
}