最小体力消耗-分支限界法

最小体力消耗-分支限界
【习题描述】
你准备参加一场徒步活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费体力最小的一条路径。

一条路径耗费的体力值是路径上相邻格子之间高度差绝对值的最大值决定的。

请你返回从左上角走到右下角的最小体力消耗值 。
【输入说明】
输入第一行有两个数字，表示rows和columns，其间用半角逗号分隔。接下来有rows行数据，每行有columns个数据。
【输入样例】
3 3
1 2 2
3 8 2
5 3 5
【输入样例】
2

【说明】
3和5的差的绝对值等于2

#include 
#include 
#include 

#define N 100

void  swap(int  *a,  int  *b)  {
        int  tmp  =  *a;
        *a  =  *b,  *b  =  tmp;
}

struct  DisjointSetUnion  {
        int  *f,  *size;
        int  n,  setCount;
};

void  initDSU(struct  DisjointSetUnion  *obj,  int  n)  {
        obj->f  =  malloc(sizeof(int)  *  n);
        obj->size  =  malloc(sizeof(int)  *  n);
        obj->n  =  n;
        obj->setCount  =  n;
        for  (int  i  =  0;  i  <  n;  i++)  {
                obj->f[i]  =  i;
                obj->size[i]  =  1;
        }
}

int  find(struct  DisjointSetUnion  *obj,  int  x)  {
        return  obj->f[x]  ==  x  ?  x  :  (obj->f[x]  =  find(obj,  obj->f[x]));
}

int  unionSet(struct  DisjointSetUnion  *obj,  int  x,  int  y)  {
        int  fx  =  find(obj,  x),  fy  =  find(obj,  y);
        if  (fx  ==  fy)  {
                return  0;
        }
        if  (obj->size[fx]  <  obj->size[fy])  {
                swap(&fx,  &fy);
        }
        obj->size[fx]  +=  obj->size[fy];
        obj->f[fy]  =  fx;
        obj->setCount--;
        return  1;
}

int  connected(struct  DisjointSetUnion  *obj,  int  x,  int  y)  {
        return  find(obj,  x)  ==  find(obj,  y);
}

struct  Tuple  {
        int  x,  y,  z;
};

int  cmp(const  struct  Tuple  *a,  const  struct  Tuple  *b)  {
        return  a->z  -  b->z;
}

int  minimumEffortPath(int  **heights,  int  row,  int  col)  {
        int  m  =  row;
        int  n  =  col;
        struct  Tuple  edges[n  *  m  *  2];
        int  edgesSize  =  0;
        for  (int  i  =  0;  i  <  m;  ++i)  {
                for  (int  j  =  0;  j  <  n;  ++j)  {
                        int  id  =  i  *  n  +  j;
                        if  (i  >  0)  {
                                edges[edgesSize].x  =  id  -  n;
                                edges[edgesSize].y  =  id;
                                edges[edgesSize++].z  =  fabs(heights[i][j]  -  heights[i  -  1][j]);
                        }
                        if  (j  >  0)  {
                                edges[edgesSize].x  =  id  -  1;
                                edges[edgesSize].y  =  id;
                                edges[edgesSize++].z  =  fabs(heights[i][j]  -  heights[i][j  -  1]);
                        }
                }
        }
        qsort(edges,  edgesSize,  sizeof(struct  Tuple),  cmp);

        struct  DisjointSetUnion  *uf  =  malloc(sizeof(struct  DisjointSetUnion));
        initDSU(uf,  m  *  n);
        int  ans  =  0;
        for  (int  i  =  0;  i  <  edgesSize;  i++)  {
                unionSet(uf,  edges[i].x,  edges[i].y);
                if  (connected(uf,  0,  m  *  n  -  1)){
						ans  =  edges[i].z;
                        break;
                }
        }
        return  ans;
}

int  main()  {
        int  row,  col;
        int  **heights;
        scanf("%d",  &row);
        scanf("%d",  &col);
        heights  =  (int  **)  malloc(sizeof(int  *)  *  row);
        for  (int  i  =  0;  i  <  row;  i++)  {
                heights[i]  =  (int  *)  malloc(sizeof(char)  *  col);
                for  (int  j  =  0;  j  <  col;  ++j)
                        scanf("%d",&heights[i][j]);
        }
        printf("%d",minimumEffortPath(heights,row,col));
        return  0;
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108