10595 - Knight on the Bee Board

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

10595 - Knight on the Bee Board

Post by subbu » Sun Jan 18, 2004 11:01 pm

Can anyone give me a few suggestions as to how to
find the moves of the knight from a given cell.

Thx.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Mon Jan 19, 2004 5:10 am

We suggested a new coordinate system (something like two diagonal axes and a vertical axis) to convert the bee board into a normal chessboard, and did a BFS to find the minimum cost. (Sorry I don't remember the details :wink:)
JongMan @ Yonsei

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

Post by subbu » Tue Jan 20, 2004 3:48 am

Whinii,

Thx a lot.
I got AC after some ugly looking code.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Jan 20, 2004 6:29 pm

After ~10 WAs, I couldn't help asking: is the input file well-formed?

Of course, it might be a mistake on my side, but, just wanna ask that... Thx :(

P.S. My code couldn't reach EOF...... I'm sure about that...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

Post by subbu » Tue Jan 20, 2004 8:56 pm

I think the file is alright.

I was reading something like

while(cin>>n) in C++.

and i had no probs.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Jan 21, 2004 3:58 am

Got accepted finally. My code fails in taking input... Forgot about the blank line after the last test case......... :lol:

Thanks for your attention!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Jan 26, 2004 6:59 am

Can someone post some inputs and outputs?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Jan 27, 2004 12:09 pm

One small hint: your knight can't get out of the bee-board (you probably have noticed that :P)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Jan 27, 2004 6:41 pm

I've took that into account..

Here's my method:
I converted it to a x, y coordinate system, and then BFS.

At each step of BFS, I check adjacent cells, and make sure that those cells are not outside of N.

Everything else is standard..

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Jan 28, 2004 12:28 am

Well, it's not much, but here's what I had in my input file

Code: Select all

70 2
11
22
7 69

70 5
41
46
10
11
22
7 69

10000 0
1 10000
Answers are 4, Impossible, and 20.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Jan 28, 2004 4:34 am

Thanks for the input, but unforunately, it solves those correctly...

Are these right? =/

For building the hex..
[c]
{ 0, 1, 1, 0, -1, -1 };
{ -1, -1, 0, 1, 1, 0 };[/c]

For BFS..
[c]
{ 2, 1, -1, -2, -3, -3, -2, -1, 1, 2, 3, 3 };
{ 1, 2, 3, 3, 2, 1, -1, -2, -3, -3, -1, -2 };
[/c]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Mar 09, 2004 12:47 pm

Code: Select all

70 3
11
22
7
7 69
What does people get for that input?

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Tue Mar 09, 2004 6:42 pm

My AC program writes 4.
JongMan @ Yonsei

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Mar 09, 2004 7:10 pm

And mine writes Impossible, so I'd guess there are no such cases. :)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Mar 10, 2004 3:27 pm

After recoding from scratch, I found my original error. I forgot a period in "impossible."

Ah well. Such a waste of time.. =)

Post Reply

Return to “Volume 105 (10500-10599)”