SPOJ.com - Problem HXH

HXH - Hunter x Hunter

no tags

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!

hide comments

< Previous 1 2 Next >

	Sergej: 2019-02-14 13:07:35 AC due to @Nadstratosfer & @Simes: Thanks.
	Simes: 2019-02-11 15:55:50 Thanks @Nadstratosfer. Finally got AC by 1) ignoring blank lines, and 2) stop processing a line on the first invalid character and leave part of the previous map in place. Bad bad bad. I wish I could give more than one thumbs down. I can't understand how so many people got accepted. Edit : there is a comment from OP that tells you to skip /n ;p [Simes]: and is that acceptable? OP should fix the bad data, not merely comment about it Last edit: 2024-07-08 11:00:54
	nadstratosfer: 2019-02-09 05:54:49 Test cases definitely contain gridlines shorter than n. Idiotic TL doesn't allow me to AC in Python so I can't give the advice how to circumvent it until I rewrite in C. Psetter, fix your stuff instead of stubbornly claiming that it's everyone else who has a problem. With 60+% of submissions being WA or RE, one'd think you can show some humility. Edit: What an unbelievable garbage. To get AC, you need to break reading the line when a char not from ".#" occurs; skip to next line and LEAVE THE REST OF THE LINE WITH DATA FROM PREVIOUS TESTCASE! That's right, filling the grid with '.' before reading or otherwise trying to make up for the missing characters gets WA! No wonder solvers from top10 can't pass this antiprogramming challenge. Edit from psetter: Idk how can you talk like that in a friendly environment just because you dont know how to get a problem solved, keep it together next time Last edit: 2022-08-09 00:24:44*
	Rocker3011: 2018-11-19 22:07:54 Hello I uploaded this problem a long long time ago, indeed the test cases have this issue: n matrix n matrix as you can see there is an extra '\n' on every test case, if you use cin, scanf, or similar you should be fine, however using gets, getchar or getline will lead to wrong answer, sorry for this inconvenient.
	Simes: 2018-06-17 12:31:55 I think there are blank lines within the grid. I assert on everything I can, and they all pass provided I ignore blank lines,. I get SIGABRT if I don't ignore blank lines. I still can't get AC though. So frustrating. Last edit: 2018-06-17 12:32:46
	vinay1998: 2018-06-08 16:20:22 @Rocker3011 I think in the test case files there exists atleast one testcase with n<=1 , because if I handle the cases for n<=1 , I get WA and if I don't then I am getting SIGSEV .Please correct this . Hello friend there is no case for n<=1, try using a standard reading character by character and not something like getline Last edit: 2018-11-19 22:10:26
	hodobox: 2017-07-16 00:03:41 Well, beats me, but I get SIGABRT, and if I add if(n<1) exit(0); I get WA. I'm simply reading input using cin. edit: when I read a character from the grid, at some point I find a digit. Which I think most probably means some character is missing from the grid and I get a new 'n' instead. But I'd love to be proven wrong and shown how my input reading is bad. P.S. I've tried some random things in the last few submissions so don't look at those for this. Last edit: 2017-07-16 00:14:29
	Sonu Bansal: 2014-03-18 17:23:04 i think there is a case where some other character is present in place of '.' so process '.' in else part edit: test data is fine, some ways to solve the problem have bundary issues, check twice Last edit: 2015-08-07 02:48:19
	(test): 2013-08-18 11:31:45 Please correct the test data as the length of each row is not exactly N (some are less than N)!
	Rocker3011: 2013-07-30 04:41:16 I had a problem with the test data, however solutions have been rejudged and no one of the accepted solutions ended in wrong answer :) there is no '#' at the end or starting point, if you are using C++, use scanf.

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