10595 - Knight on the Bee Board

subbu · 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. · 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

)

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

Whinii,

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

Observer · 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...

subbu · 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 · 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.........

Thanks for your attention!

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

Can someone post some inputs and outputs?

Observer · 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

)

Larry · 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 · 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

Answers are 4, Impossible, and 20.

Larry · 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 · Post by **Larry** » Tue Mar 09, 2004 12:47 pm

Code: Select all

What does people get for that input?

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

My AC program writes 4.

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

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

Larry · 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.. =)