SPOJ.com - Problem HXH

HXH - Hunter x Hunter

Gon and Killua are two very talented hunters, and they are also very skilled fighters, however it is well known that Killua is faster and smarter than Gon, and Gon is stronger and is way more decided than Killua. That makes them almost the perfect team (they just need more time to become the most skilled hunters that ever lived) and they are so good as a team that they decided to fight and defeat many enemies (as much as they can) so they made a plan, as the enemies are in a N x N grid Gon decided to start at position 0,0 of this grid and Killua at position n-1,n-1. To maximize the number of defeated enemies Gon moves only to the Right and Down, and Killua to the Left and Up, they count how many enemies they defeated and stop when both of them are in the same cell and they give each other a high five. So if they complete the ride without doing this they will be mad, so that will not be a solution.

However Killua wants this to be perfect, so he is tracing a new plan, but he does not know the best ride, as you are an amazing programmer he asked you for your help and you need to give him the maximum amount of enemies they can defeat together and then give each other a high five, only with this information the super brain of Killua will figure out the rest.

Remember, the ride will not finish if they do not give each other that high five.

The grid has this properties:

‘#’ is an obstacle that neither Gon nor Killua can pass through.
‘.’ is a walkable area.
‘*’ is an enemy.

Also they move at the same time, if any of them cannot move, it will not be a valid move. They never stand still.

Input

The input consist on several test cases represented by T each of them start with an 2 <= N <= 500 the size of the grid and the grid itself.

Output

Just show the maximum number of enemies that both can defeat, and then give each other a high five. If this cannot be done print -1.

Sample

Input:
1
5
..*..
.*..*
#...*
..*..
.....

Output:
3

They could defeat all 5 if they weren’t going to give each other a high five, but as they do and they never stand still, they will defeat only 3 and then give a high five, Killua defeats 2 and Gon 1.

Submit solution!

Added by:	Rocker3011
Date:	2013-07-01
Time limit:	0.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64

hide comments

2013-07-24 09:16:04 (test)
Test cases do include '#' and '*' at the starting positions (0,0) and (N-1, N-1). When either starting position is '#', they can't give each other high five, right? When starts at '*', is this enemy counted? When they meet, if there is an enemy there, is it counted once or twice (killed by both)?

Edit: Hello there is not # on the starting or end point, but sure there is some '*' and of course they count :)

Edit: Thanks for the reply. However, as my submission got SIGABRT (due to the failure of assertion), there exists at least one test case that has a '#' in either or both of the starting positions. Please verify it.

How about my last question? Do the enemy counted as one or two?

Edit: Hi, i checked the input and there is not such case. I am sorry, if one of them defeats an enemy the other one will not defeat the same enemy, you can consider that every enemy is defeated once (so each of them are counted only once)

Edit: I asserted this time to make sure each row of the grid read has the length N. However, this assertion failed. Please tell me what's wrong with my input reading code. My submission id is 9747287. Thanks.

I asked the last question because they move at the same time. :)

Last edit: 2013-07-30 03:33:12

2013-07-22 22:36:26 Taym
Please, what is the complexity of this problem? I've solved it in O(n*n) but I'm still getting "time limit exceeded".

Edit: That is the actual complexity of the problem
Thanks.

Last edit: 2013-07-23 23:50:39

2013-07-18 13:29:41 Xsquare
WA.. Any tricky cases~!?

2013-07-17 15:50:41 Haijun Deng
WA, Any tricky cases?