比赛 |
20120712 |
评测结果 |
AAAAAAAAAA |
题目名称 |
登山 |
最终得分 |
100 |
用户昵称 |
CC |
运行时间 |
0.098 s |
代码语言 |
C++ |
内存使用 |
0.37 MiB |
提交时间 |
2012-07-12 11:16:02 |
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <cstring>
struct coor {
int x,y;
}pre[70][70];
const int dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};
int n,m,ans,res;
int a[70][70],dis[70][70];
bool done[70][70];
void dfs(int x,int y) {
int p,q;
ans = std::max(ans,dis[x][y]);
for (int i = 0;i < 4;i++) {
p = x + dx[i];q = y + dy[i];
if (!done[p][q] && a[p][q] < a[x][y]) {
if (dis[p][q] < dis[x][y] + 1) {
dis[p][q] = dis[x][y] + 1;
pre[p][q].x = x,pre[p][q].y = y;
dfs(p,q);
}
}
}
}
void solve(int x,int y) {
int tmp;
memset(dis,0,sizeof(dis));
memset(pre,0,sizeof(pre));
memset(done,0,sizeof(done));
ans = 0;
dfs(x,y);
tmp = ans;
bool ok = 1;
for (int i = 1;i <= n;i++) {
if (!ok) break;
for (int j = 1;j <= m;j++) if (dis[i][j] == ans) {
int p = i,pp = i,q = j,qq = j;
while (p && q) {
done[p][q] = 1;
p = pre[pp][qq].x;q = pre[pp][qq].y;
pp = p;qq = q;
}
ok = 0;
break;
}
}
memset(dis,0,sizeof(dis));
ans = 0;
dfs(x,y);
tmp += ans;
tmp++;
res = std::max(res,tmp);
}
int main() {
freopen("hike.in","r",stdin);
freopen("hike.out","w",stdout);
scanf("%d%d", &n, &m);
memset(a,61,sizeof(a));
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++) scanf("%d", &a[i][j]);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++) solve(i,j);
printf("%d\n", res);
return 0;
}