比赛 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;
}