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