PROBLEM LINK:
Author: Bhushan Khanale
DIFFICULTY:
Easy-Medium
PREREQUISITES:
DFS
PROBLEM:
The problem was to find the total number of ink blocks at the end of the ink-dropping procedure.
QUICK EXPLANATION:
The solution concept is quite simple, we find the prime numbers and then do a DFS to visit the longest chain of overlapping/connected blocks of ink. Finally while doing so keep a count of the blocks we are looking into. The final answer will be the count generated.
EXPLANATION:
The problem tells us that for every prime number in the grid we will put an ink drop over to it. Also the ink drop will ‘spread’ and cover all the adjacent elements of the prime number in the grid. It is given that, when two ink blocks overlap each other, they form a single ink block. Hence if the adjacent elements are common in two ink blocks, they constitute to the same ink block. From this we can generate the idea of DFS. Since the ink blocks can be considered as nodes and then the connection will denote the edge between those. We can find out the primes through the sieve and then we can check for the unique block by the source of DFS as the source should be unvisited and should be a prime number. Further such number of sources for the DFS should be counted, which would be our required answer.
Please have a look at @abdullah768 solution given below, which is easy to understand the approach.