forked from zhuli19901106/poj
-
Notifications
You must be signed in to change notification settings - Fork 0
/
POJ1008(AC).cpp
89 lines (78 loc) · 1.37 KB
/
POJ1008(AC).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
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
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
int r, c, maxlen;
int h[105][105];
int len[105][105];
int d[4][2] = {
{-1, 0},
{+1, 0},
{ 0, -1},
{ 0, +1}
};
const int INF = 99999;
typedef struct st{
int i;
int j;
int h;
}st;
st v[10005];
int comparator(const void *a, const void *b)
{
const st *sa, *sb;
sa = (const st *)a;
sb = (const st *)b;
if(sa->h > sb->h){
return 1;
}else{
return -1;
}
}
int main()
{
int i, j, k;
while(true){
if(scanf("%d%d", &r, &c) != 2){
break;
}
for(i = 0; i <= r + 1; ++i){
for(j = 0; j <= c + 1; ++j){
h[i][j] = INF;
}
}
k = 0;
for(i = 1; i <= r; ++i){
for(j = 1; j <= c; ++j){
scanf("%d", &h[i][j]);
v[k].i = i;
v[k].j = j;
v[k].h = h[i][j];
++k;
len[i][j] = 0;
}
}
qsort(v, r * c, sizeof(st), comparator);
for(i = 0; i < r * c; ++i){
for(k = 0; k < 4; ++k){
if(
h[v[i].i][v[i].j] < h[v[i].i + d[k][0]][v[i].j + d[k][1]]
&& len[v[i].i][v[i].j] >= len[v[i].i + d[k][0]][v[i].j + d[k][1]]
){
len[v[i].i + d[k][0]][v[i].j + d[k][1]] = len[v[i].i][v[i].j] + 1;
}
}
}
maxlen = 0;
for(i = 0; i < r * c; ++i){
if(len[v[i].i][v[i].j] > maxlen){
maxlen = len[v[i].i][v[i].j];
}
}
printf("%d\n", maxlen + 1);
}
return 0;
}