Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2014
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.92 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <math.h>
  5.  
  6. long long heap[1100000 + 1][2];
  7. long long len = 1;
  8. long long inf = 1000000000000;
  9.  
  10. void swap(long long *a, long long *b) {
  11.     long long t = *a;
  12.     *a = *b;
  13.     *b = t;
  14. }
  15.  
  16. long long pop_min(void) {
  17.     long long ans = heap[1][1];
  18.     long long k = 1;
  19.     swap(&heap[k][0], &heap[len - 1][0]);
  20.     swap(&heap[k][1], &heap[len - 1][1]);
  21.     --len;
  22.     heap[len][0] = inf;
  23.     int f = 1;
  24.     while ((k*2) <= len && f) {
  25.         f = 0;
  26.         if (heap[k][0] > heap[k*2][0] && heap[k*2][0] <= heap[k*2 + 1][0]) {
  27.             swap(&heap[k][0], &heap[k*2][0]);
  28.             swap(&heap[k][1], &heap[k*2][1]);
  29.             k <<= 1;
  30.             k *= 2;
  31.             f = 1;
  32.         } else
  33.             if (heap[k][0] > heap[k*2+ 1][0] && heap[k*2][0] >= heap[k*2 + 1][0]) {
  34.             swap(&heap[k][0], &heap[k*2 + 1][0]);
  35.             swap(&heap[k][1], &heap[k*2 + 1][1]);
  36.             k = k*2 + 1;
  37.             f = 1;
  38.         }
  39.     }
  40.     return ans;
  41. }
  42.  
  43. void add(long long x, long long y) {
  44.     heap[len][0] = x;
  45.     heap[len][1] = y;
  46.     long long cur = len;
  47.     while ((cur > 1) && (heap[cur][0] < heap[cur / 2][0])) {
  48.         swap(&heap[cur][0], &heap[cur / 2][0]);
  49.         swap(&heap[cur][1], &heap[cur / 2][1]);
  50.         cur = cur / 2;
  51.     }
  52.     len++;
  53. }
  54.  
  55. long long Min(long long a, long long b){
  56.     return (a < b) ? a : b;
  57. }
  58.  
  59. int main(void){
  60.     int MAXN = 1100000 + 1;
  61.     int i,j,n,m,sx,sy,fx,fy;
  62.     scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&fx,&fy);
  63.     int **a = (int **) malloc(n * sizeof(int));
  64.     for (i = 0; i < n; i ++) {
  65.         a[i] = (int *) malloc(m * sizeof(int));
  66.     }
  67.     long long d[MAXN];//take[MAXN];
  68.     for (i = 0; i < n; ++i){
  69.         for (j = 0; j < m; ++j){
  70.             int c = 0;
  71.             scanf("%d",&c);
  72.             a[i][j] = c;
  73.         }
  74.     }
  75.     for (i = 0; i < n * m; ++i){
  76.         d[i] = inf;
  77.        // take[i] = 1;
  78.     }
  79.     d[sx*m + sy] = 0;
  80.     add(0,sx*m + sy);
  81.     const int pos[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
  82.     while (len > 1){
  83.         long long curx = 0, cury =  0;
  84.     //    long long min = inf;
  85.       /*  for (i = 0; i < nm; ++i){
  86.             if (d[i] < min && take[i]){
  87.                 min = d[i];
  88.                 curx = i / m;
  89.                 cury = i % m;
  90.             }
  91.         }*/
  92.         long long t = pop_min();
  93.         curx = t / m;
  94.         cury = t % m;
  95.  
  96.         for (i = 0; i < 4; ++i){
  97.             if ((curx + pos[i][0] >= 0) && (curx + pos[i][0] < n) && (cury + pos[i][1] >= 0) && (cury + pos[i][1] < m)){
  98.                 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])){
  99.                     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]);
  100.                     add(d[(curx + pos[i][0])*m + cury + pos[i][1]],(curx + pos[i][0])*m + cury + pos[i][1]);
  101.                 }
  102.             }
  103.         }
  104.         //take[curx*m + cury] = 0;
  105.     }
  106.     printf("%lld",d[m*fx + fy]);
  107.     return 0;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement