Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <math.h>
- long long heap[1100000 + 1][2];
- long long len = 1;
- long long inf = 1000000000000;
- void swap(long long *a, long long *b) {
- long long t = *a;
- *a = *b;
- *b = t;
- }
- long long pop_min(void) {
- long long ans = heap[1][1];
- long long k = 1;
- swap(&heap[k][0], &heap[len - 1][0]);
- swap(&heap[k][1], &heap[len - 1][1]);
- --len;
- heap[len][0] = inf;
- int f = 1;
- while ((k*2) <= len && f) {
- f = 0;
- if (heap[k][0] > heap[k*2][0] && heap[k*2][0] <= heap[k*2 + 1][0]) {
- swap(&heap[k][0], &heap[k*2][0]);
- swap(&heap[k][1], &heap[k*2][1]);
- k <<= 1;
- k *= 2;
- f = 1;
- } else
- if (heap[k][0] > heap[k*2+ 1][0] && heap[k*2][0] >= heap[k*2 + 1][0]) {
- swap(&heap[k][0], &heap[k*2 + 1][0]);
- swap(&heap[k][1], &heap[k*2 + 1][1]);
- k = k*2 + 1;
- f = 1;
- }
- }
- return ans;
- }
- void add(long long x, long long y) {
- heap[len][0] = x;
- heap[len][1] = y;
- long long cur = len;
- while ((cur > 1) && (heap[cur][0] < heap[cur / 2][0])) {
- swap(&heap[cur][0], &heap[cur / 2][0]);
- swap(&heap[cur][1], &heap[cur / 2][1]);
- cur = cur / 2;
- }
- len++;
- }
- long long Min(long long a, long long b){
- return (a < b) ? a : b;
- }
- int main(void){
- int MAXN = 1100000 + 1;
- int i,j,n,m,sx,sy,fx,fy;
- scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&fx,&fy);
- int **a = (int **) malloc(n * sizeof(int));
- for (i = 0; i < n; i ++) {
- a[i] = (int *) malloc(m * sizeof(int));
- }
- long long d[MAXN];//take[MAXN];
- for (i = 0; i < n; ++i){
- for (j = 0; j < m; ++j){
- int c = 0;
- scanf("%d",&c);
- a[i][j] = c;
- }
- }
- for (i = 0; i < n * m; ++i){
- d[i] = inf;
- // take[i] = 1;
- }
- d[sx*m + sy] = 0;
- add(0,sx*m + sy);
- const int pos[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
- while (len > 1){
- long long curx = 0, cury = 0;
- // long long min = inf;
- /* for (i = 0; i < nm; ++i){
- if (d[i] < min && take[i]){
- min = d[i];
- curx = i / m;
- cury = i % m;
- }
- }*/
- long long t = pop_min();
- curx = t / m;
- cury = t % m;
- for (i = 0; i < 4; ++i){
- if ((curx + pos[i][0] >= 0) && (curx + pos[i][0] < n) && (cury + pos[i][1] >= 0) && (cury + pos[i][1] < m)){
- if (d[(curx + pos[i][0])*m + cury + pos[i][1]] > d[curx*m + cury] + abs(a[curx + pos[i][0]][cury + pos[i][1]] - a[curx][cury])){
- d[(curx + pos[i][0])*m + cury + pos[i][1]] = d[curx*m + cury] + abs(a[curx + pos[i][0]][cury + pos[i][1]] - a[curx][cury]);
- add(d[(curx + pos[i][0])*m + cury + pos[i][1]],(curx + pos[i][0])*m + cury + pos[i][1]);
- }
- }
- }
- //take[curx*m + cury] = 0;
- }
- printf("%lld",d[m*fx + fy]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement