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
I haven't read your code, but bfs seems an overkill. If I understand correctly the problem, then you only have to check 4 cells for each firework, and flag them exploded. If it hasn't been exploded yet, then increase the count by one.
1 small question,the value of 'n' in the question can vary from 1 to 1000,but,when the value of n is 1000,then an array of 1000*1000 size is to be created.Will this not lead to a memory overflow?How to handle this type of scenario?
Don't worry. It won't overflow as long as you use static(global) declarations of arrays.
So I should simply write arr[1000][1000] outside main? This might be a silly question.(I am new to C.P.)
Yeah, just write that outside "int main()" and it will be OK.
Your time complexity is O(n^4) so it is obvious that you get a TLE.
You can solve the problem like this:
DFS(or BFS) the whole grid once to calculate which connected component each cell belongs to, and the size of each connected component.
For each firework, get the set of the connected component of the 4 adjacent cells, and simply calculate the sum of there sizes.
The sample case work like this:
F11F
11F2
F11F
F11F
(F=firework)
The size of the first connected component('1' grid): 8
The size of the second connected component('2' grid): 1
Firework 1: 8('1' grid)+1(itself)
Firework 2: 8('1' grid)+1('2' grid)+1(itself)
(And so on)
(Don't forget to use 64-bit integers as 32-bit integers might overflow)
(Sorry for my poor English)
Thanks for the answer.
1.)So,I should put the first empty cell in my queue and put 1 in all the cells reachable from my current cell,then again find an empty cell until I find another empty cell,and repeat the same process.
2.)Then for each firework,add all the size of the different numbers adjacent to it.
The time complexity for 1.) is O(n^2),for the second point,for each F,then for each number,search the whole grid,so it would be O(n^3).Right?
In fact, in the second part, for each F we only need to consider 4 cells and simply add the sizes which are already calculated instead of do DFS(BFS) for another time. So it would be O(4*n^2)=O(n^2).
But,how will I number every cell with just 1 BFS traversal.
Let us assume I got the first empty cell,called BFS for it and marked all cells as 1 which were connected to it.For finding empty cells which were left,I have to traverse the grid again.So would it be O(n^4)?
As simple as those below:
for i=first to last for j=first to last if(not visited(cell[i][j]) bfs from (i,j)
Each cell is traversed at most once, so it's O(n^2) in total.
2nd question of Hiring Challenge!