10923 - Seven Seas

Dreamer#1 · Post by **Dreamer#1** » Sat Oct 01, 2005 6:06 pm

I think I'm missing something in this problem. I saw dozens of people solved it in online contest but I find the problem unclear.

The enemy ships are pretty dumb, so that they will always move to the closest position they can get to you, ...

Consider the following situation at some portion of the board after my move:

Code: Select all

S..
..E

Now where will the E move? There are two possibilities:

Code: Select all

SE.
...

OR,

S..
.E.

Can someone please explain which one should we consider and why?

Thanks in advance.

Dreamer#1 · Post by **Dreamer#1** » Sun Oct 02, 2005 3:02 am

sorry i forgot to login...

liux0229 · Post by **liux0229** » Sun Oct 02, 2005 5:52 am

hi, Dreamer#1!
It was my post. Although I knew it was euclidean distance but I've kept getting WA since the contest. I was here for some hint on where could be wrong but only to find your post. Since you've got AC, can you post some input/output here?

CodeMaker · Post by **CodeMaker** » Sun Oct 02, 2005 9:25 pm

not much......but u can try this.
input:

Code: Select all

7

........
........
........
.#E...E#
.#.....#
.#.....#
.#S....#
.#######
........

E......E
........
........
........
...S....
........
........
........
E......E


........
........
........
.#E...E#
.#.#.#.#
.#.###.#
.#S....#
.#######
........

........
...#....
........
..#.....
........
........
..S.....
........
........

........
.E.#....
...E....
..#.....
........
........
..S.....
........
........

........
.E.E....
...S....
.E..E...
........
........
........
........
........

E......#
........
........
........
........
........
........
.......S
#.......

output:

Code: Select all

I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
Oh no! I'm a dead man!

liux0229 · Post by **liux0229** » Mon Oct 03, 2005 11:58 am

Sorry, it was me

shanto86 · Post by **shanto86** » Wed Oct 05, 2005 9:20 am

is the soln a straight forward BFS?? but 8^10 is much bigger (in worst case) nay kinda huristic needed??

wook · Post by **wook** » Wed Oct 05, 2005 9:29 am

shanto86 wrote:is the soln a straight forward BFS?? but 8^10 is much bigger (in worst case) nay kinda huristic needed??

no, wise DFS (recursive) is enough.

Emilio · Post by **Emilio** » Thu Oct 06, 2005 10:44 pm

Hello there!

I have got correct answers for all the inputs of this board, but I get WA from OJ.

Could anyone say me if are there some tricky inputs?
And, could anyone say me if is this correct?

input:

Code: Select all

8	
.....S..
........
........
########
E......E
........
....E...
........
EEE.....

.....S..
........
........
........
E......E
........
....E...
........
..E.....

.....S..
........
........
........
........
........
........
E......E
........

.....S..
........
........
........
E......E
........
........
........
........

.....S..
........
........
........
........
E......E
........
........
........

E....S..
........
........
........
........
........
....E...
........
EEE.....

.....S..
........
........
........
........
..E.....
....E...
........
........

.....S..
........
.....#..
........
........
..E.....
....E...
........
........

output:

Code: Select all

I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!

Thanks in advance!

Cho · Post by **Cho** » Fri Oct 07, 2005 3:17 am

My output:

Code: Select all

I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!

No trick at all. A simple DFS will do.

[EDIT:] Please ignore my output, it's wrong and Emilio's output is correct.

Emilio · Post by **Emilio** » Fri Oct 07, 2005 8:16 pm

Hi another time!

I can't figure out how you can destroy the enemies in the fourth case without dead.
Could you explain me that?

little joey · Post by **little joey** » Fri Oct 07, 2005 10:14 pm

Strange, my program gives the same answers as Emilio's.
I'd be interested how the ship can escape in cases 4 and 6.

krijger · Post by **krijger** » Fri Oct 07, 2005 10:50 pm

My AC program also gives the same answers as Emilio's.

btw. In case 4 you can escape if you allow the ship to go 'outside the area', but I don't see how you can escape in case 6.

Emilio · Post by **Emilio** » Sat Oct 08, 2005 1:52 am

Thanks!

I have got AC. My trouble was a bug in my code.

But I have got AC with different approachs:
1. I calculate the distance how euclidean distance.
2. I calculate the distance how Manhattan distance.
3. I can move (only test with my own ship) where there is a rock.
4. I can't move (only test with my own ship) where there is a rock.
5. A mixture of them.

Strange?

I think test cases are poor or other things...

Cho · Post by **Cho** » Sat Oct 08, 2005 8:59 am

There is a bug in my previously AC-ed code, so the output of my previous post is wrong.

Solaris · Post by **Solaris** » Mon Feb 06, 2006 10:10 am

This code runs ok in my VC 6.0 but shows CE in the OJ ... I have removed the sort function and then the CE is removed. Can any one tell me why this happens ?? (I have overloaded the < operator, and this should run ok, I want to know why not)

Code: Select all

You do not want to get AC in 1.5 seconds in this problem

I have already got AC in this problem by omitting the sort function. But I am surprised to see some near zero second solves in this problem. Is there any greedy approach (or any other approach than DFS) to solve this problem ?? Thanx in advance for any hint that anyone can give.

Perdon my bad english