posts - 74,  comments - 33,  trackbacks - 0

Description

The cows have revised their game of leapcow. They now play in the middle of a huge pasture upon which they have marked a grid that bears a remarkable resemblance to a chessboard of N rows and N columns (3 <= N <= 365).

Here's how they set up the board for the new leapcow game:

* First, the cows obtain N x N squares of paper. They write the integers from 1 through N x N, one number on each piece of paper.

* Second, the 'number cow' places the papers on the N x N squares in an order of her choosing.

Each of the remaining cows then tries to maximize her score in the game.

* First, she chooses a starting square and notes its number.

* Then, she makes a 'knight' move (like the knight on a chess board) to a square with a higher number. If she's particularly strong, she leaps to the that square; otherwise she walks.

* She continues to make 'knight' moves to higher numbered squares until no more moves are possible.

Each square visited by the 'knight' earns the competitor a single point. The cow with the most points wins the game.

Help the cows figure out the best possible way to play the game.

Input

* Line 1: A single integer: the size of the board

* Lines 2.. ...: These lines contain space-separated integers that tell the contents of the chessboard. The first set of lines (starting at the second line of the input file) represents the first row on the chessboard; the next set of lines represents the next row, and so on. To keep the input lines of reasonable length, when N > 15, a row is broken into successive lines of 15 numbers and a potentially shorter line to finish up a row. Each new row begins on its own line.

Output

* Line 1: A single integer that is the winning cow's score; call it W.

* Lines 2..W+1: Output, one per line, the integers that are the starting square, the next square the winning cow visits, and so on through the last square. If a winning cow can choose more than one path, show the path that would be the 'smallest' if the paths were sorted by comparing their respective 'square numbers'.

Sample Input

4
1 3 2 16
4 10 6 7
8 11 5 12
9 13 14 15

Sample Output

72459101213
本以为最长上升子序列,没错,最长的步数对了,但是因为路径更新有无,所以还是一直Wrong Answer。。。。无语


 

代码AC后更新

posted on 2008-12-23 21:52 KNIGHT 阅读(371) 评论(2)  编辑 收藏 引用

FeedBack:
# re: poj 2111 Millenium Leapcow
2008-12-23 23:22 | Knight
如果你能接受这个
3160K 1047MS C++ 1547B
真的很烦,居然1047ms一般都是200ms左右我居然这么多,晕
思路还是最长上升子序列
不过更新路径的函数代码如下
int cmp(int a,int b)
{
if(pre[a]==a)
{
if(a>b)return 1;
else if(a==b)return 0;
else return -1;
}
else
{
int t=cmp(pre[a],pre[b]);
if(t==0)
{
if(a>b)return 1;
else if(a==b)return 0;
else return -1;
}
else return t;
}
}
********************************
即如果路径长度相同的话,就执行cmp从而判断字典序!更新字典序!很浪费时间!
********************************  回复  更多评论
  
# re: poj 2111 Millenium Leapcow
2008-12-24 12:43 | Knight
鱿鱼大牛的思路
从n*n开始搜索到1结束DP更新路径
排名20 3160K 157MS C++ 1228B
还行经典代码如下:
for(i=M;i>=1;i--)
{
for(j=0;j<8;j++)
{
int x=num[i].x+dir[j][0];
int y=num[i].y+dir[j][1];
if(OK(x,y,i))
{
if(num[i].max+1>num[map[x][y]].max)
{
num[map[x][y]].max=num[i].max+1;
pre[map[x][y]]=i;
}
else if(num[i].max+1==num[map[x][y]].max&&i<pre[map[x][y]])
pre[map[x][y]]=i;
}
}
if(MAX<=num[i].max)
{
MAX=num[i].max;
sign=i;
}
}  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2008年12月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜