Game | HackerEarth

Game

Practice

4.6 (10 votes)

Algorithms

Depth first search

Graphs

Medium

Problem

61% Success 1794 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

You are playing a game in which you have a rectangular grid of n*n 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 Format: The first line contains an integer n denoting the dimensions of the grid. Each of the next n lines contains symbols: "." for empty cells, "*" for cells containing a firework. Note: All rows have n number of symbols. Output Format: Print the sum of the number of cells destroyed if each bomb is triggered independently. Input Constraints: \(1 \le n \le 1000\)

Sample Input

4
*..*
..*.
*..*
*..*

Sample Output

Explanation

Here n = 4. So given grid A is of \(4 \times 4\) size. Considering indexing starts from 1 in the grid: 1) A[1][1] has firework , so it will destroy all the 8 empty cells connected to it and including itself, it will destroy 9 cells in total. 2) A[1][4] has firework , so it will destroy all the 9 empty cells connected to it and including itself, it will destroy 10 cells in total. 3) A[2][3] has firework , so it will destroy all the 9 empty cells connected to it and including itself, it will destroy 10 cells in total. 4) A[3][1] has firework , so it will destroy all the 8 empty cells connected to it and including itself, it will destroy 9 cells in total. 5) A[3][4] has firework , so it will destroy all the 9 empty cells connected to it and including itself, it will destroy 10 cells in total. 6) A[4][1] has firework , so it will destroy all the 8 empty cells connected to it and including itself, it will destroy 9 cells in total. 7) A[4][4] has firework , so it will destroy all the 8 empty cells connected to it and including itself, it will destroy 9 cells in total. So total cells destroyed will be 9+10+10+9+10+9+9 = 66.

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor