-
Notifications
You must be signed in to change notification settings - Fork 0
/
otog447.cpp
40 lines (40 loc) · 979 Bytes
/
otog447.cpp
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
#include <bits/stdc++.h>
using namespace std;
int x[] = {1,0,-1,0};
int y[] = {0,1,0,-1};
int a[56][56];
int i,j;
int n,sx,sy,ex,ey;
struct node{
int x,y,val;
bool l;
bool operator < (node t) const{
return t.val < val;
}
}t;
int visit[56][56][2];
priority_queue<node> pq;
int main(){
scanf("%d",&n);
for (i = 1; i <= n; i++){
for (j = 1; j <= n; j++){
scanf("%d",&a[i][j]);
}
}
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
pq.push({sx,sy,0,0});
while (!pq.empty()){
t = pq.top(); pq.pop();
if (t.x == ex && t.y == ey && t.l){
printf("%d",t.val);
return 0;
}
if (visit[t.x][t.y][t.l]) continue;
visit[t.x][t.y][t.l] = true;
for (i = 0; i < 4; i++){
int X = t.x+x[i], Y = t.y+y[i];
if (a[X][Y] > 0) pq.push({X,Y,t.val+a[X][Y],t.l});
else if (a[X][Y] < 0) pq.push({X,Y,t.val-a[X][Y],!t.l});
}
}
}