|
|
思路： 先按棋盘上的值从大到小排序。 然后先解决值大的，再解决值小的。 注意路径的比较。应该很容易WA的。
 #include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX_N 512
  struct seq_node  {
 short y, x;
 };
struct map_node {
int val, cnt;
struct map_node *pre;
};
struct map_node map[MAX_N][MAX_N], *ans;
struct seq_node seq[MAX_N*MAX_N];
int N;
int cmp_seq(const void *a, const void *b)
{
return map[((struct seq_node *)a)->y][((struct seq_node *)a)->x].val -
map[((struct seq_node *)b)->y][((struct seq_node *)b)->x].val;
}
inline int cmp_path(struct map_node *a, struct map_node *b)
{
  while (a && b) {
if (a->val != b->val)
return a->val - b->val;
a = a->pre;
b = b->pre;
 }
return 0;
}
inline void update(struct map_node *a, int y2, int x2)
{
struct map_node *b = &map[y2][x2];
if (y2 < 0 || y2 >= N || x2 < 0 || x2 >= N)
return ;
if (b->val > a->val &&
(b->cnt > a->cnt || b->cnt == a->cnt && cmp_path(b, a->pre) < 0)
)
{
a->cnt = b->cnt;
a->pre = b;
}
}
int main()
{
int x, y, i;
struct seq_node *t;
struct map_node *m;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &N);
i = 0;
for (y = 0; y < N; y++) {
for (x = 0; x < N; x++) {
scanf("%d", &map[y][x].val);
seq[i].y = y;
seq[i].x = x;
i++;
}
}
qsort(seq, N*N, sizeof(seq[0]), cmp_seq);
for (t = &seq[N*N - 1]; t >= seq; t--) {
m = &map[t->y][t->x];
update(m, t->y - 2, t->x + 1);
update(m, t->y + 2, t->x + 1);
update(m, t->y - 2, t->x - 1);
update(m, t->y + 2, t->x - 1);
update(m, t->y - 1, t->x + 2);
update(m, t->y + 1, t->x + 2);
update(m, t->y - 1, t->x - 2);
update(m, t->y + 1, t->x - 2);
m->cnt++;
if ((!ans || m->cnt > ans->cnt) ||
(m->cnt == ans->cnt && cmp_path(m, ans) < 0)
)
ans = m;
}
printf("%d\n", ans->cnt);
while (ans) {
printf("%d\n", ans->val);
ans = ans->pre;
}
return 0;
}
|