11953 - Battleships

[faraa_T]

oh!!!!
yessss.
super silly mistake
Thank's a lot.
But why?
Why it causes time limit?!!

[shuvokr]

because when you write

int r = x + ar[0];
int c = x + ar[1];

here y have no change. As a result
if (x == (grid.length - 1) || y == (grid.length - 1) || x == 0 || y == 0 || grid[x][y] == '.')
this line y == (grid.length - 1) and y == 0 condition don't work any time and for this cause you got TLE,
And another things is
First judge cheak that there is any TLE, if there is not occurs TLE
then judge its wrong or right.

[faraa_T]

Thank you so much
Thank you very very much...

[jddantes]

[AC]

[brianfry713]

Try input:

Code: Select all

1
6
x@x...
......
......
......
......
......

Output should be 1.

[jddantes]

Right, thanks

[uDebug]

brianfry713,

Thanks for the test cases.

Here's some input I found useful during testing / debugging.

http://www.udebug.com/UVa/11953

[prnvkrjha]

Ok... So my simple flood fill solution has been accepted with DFS in all four directions.
But I am confused about this line in the question...
"Ships in battleship game can vary in size from 1 × 1 to 1 × N/2"
And I don't think my solutions adheres to this condition!

Also here. http://www.udebug.com/UVa/11953

8
@@@..@..
.....x..
..x..xx@
x..@x...
x.@x.xx.
.......x
@@.....x
..x.@...

For this test case ... the ans should be 9 (given the width of each ship is 1)
but it says 7.

[Dominik Michniewski]

According to problem statement your case is incorrect.
Ships can be placed only horizontally or vertically, but look at bolded places - there are incorrectly placed ships.

8
@@@..@..
.....x..
..x..xx@
x..@x...
x.@x.xx.
.......x