Posted on 2007-05-19 22:19
ZelluX 阅读(378)
评论(0) 编辑 收藏 所属分类:
Algorithm
5.19
第一反应觉得是个简单的BFS，从最高点开始向四周扩展，最后找到最长的路径即可。
结果Wrong Answer，仔细一想，才意识到并不一定是从最高点开始的。考虑得太不周到了。。
5.31
原来的程序找不到了。。。重新写了一遍，居然写好提交就AC了，恩。这几天进步挺大哈
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_HEIGHT = 10000;
const int MAX_ROWS = 100;
const int dx[] = 
{0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
struct Point {
int x;
int y;
int height;
};
bool comparePoints(const Point& p1, const Point& p2);
int main() {
//ifstream fin("pku1088.in");
int c, r;
int i, j;
cin >> r >> c;
int h[MAX_ROWS + 2][MAX_ROWS + 2];
int count = 0;
vector<Point> points;
for (i = 1; i <= r; i++) {
for (j = 1; j <= c; j++) {
cin >> h[i][j];
Point temp;
temp.x = i;
temp.y = j;
temp.height = h[i][j];
points.push_back(temp);
}
}
sort(points.begin(), points.end(), comparePoints);
for (i = 0; i <= c; i++) {
h[0][i] = MAX_HEIGHT + 1;
h[r + 1][i] = MAX_HEIGHT + 1;
}
for (i = 0; i <= r; i++) {
h[i][0] = MAX_HEIGHT + 1;
h[i][c + 1] = MAX_HEIGHT + 1;
}
int f[MAX_ROWS + 1][MAX_ROWS + 1];
for (i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++) {
f[i][j] = 1;
}
}
vector<Point>::iterator iter;
for (iter = points.begin(); iter != points.end(); iter++) {
for (i = 0; i < 4; i++) {
int nx = iter->x + dx[i];
int ny = iter->y + dy[i];
if (iter->height > h[nx][ny]) {
if (f[iter->x][iter->y] + 1 > f[nx][ny]) {
f[nx][ny] = f[iter->x][iter->y] + 1;
}
}
}
}
int best = 0;
for (i = 1; i <= r; i++) {
for (j = 1; j <= c; j++) {
if (f[i][j] > best) {
best = f[i][j];
}
}
}
cout << best << endl;
return 0;
}
bool comparePoints(const Point& p1, const Point& p2) {
return (p1.height > p2.height);
}