BFS Code not passing all test cases

Revision en4, by ss_96, 2017-09-10 11:02:29

I was trying to solve the following question:

You are playing a game in which you have a rectangular grid of nn cells. Each cell is either empty or has a firework. Empty cells are marked with ".", cells with firework are marked with "" . Two cells are said to be adjacent if they share a side.

If firework in any cell explodes it destroys itself and the empty cells connected to it. Two cells are connected if there is a path of empty adjacent cells between them. You have to find the number of cells that will be destroyed if the fireworks are triggered independently. Input Constraints: 1≤n≤1000 Sample Input 4

* . . *

. . * .

* . . *

* . . *

Sample Output 66(9(for 1st *)+10+10+9+10+9+9(for 7th *)).

I simply applied a BFS and added individual sum.The problem is that it only passed some test cases,wrong answer and time limit exceeded in some.Can some please suggest what test case am I missing in handling? My code: https://gist.github.com/Sharma96/16071e66b0a36828c3566196289f0c92

Tags #c++, #algorithms, #graph, bfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English ss_96 2017-09-10 11:02:29 4
en3 English ss_96 2017-09-10 10:06:17 3 Tiny change: 'nput 4\n\n* . . *\n\' -> 'nput 4\n\n\* . . *\n\'
en2 English ss_96 2017-09-10 10:04:52 0 (published)
en1 English ss_96 2017-09-10 10:04:09 1042 Initial revision (saved to drafts)