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.
hide comments
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.
|
|
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.
|
|
Rocker3011:
2018-11-19 22:07:54
Hello I uploaded this problem a long long time ago, indeed the test cases have this issue:
|
|
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 .
|
|
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.
|
|
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
|
|
(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 :)
|
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 |