Pablo has a square chocolate Box of size n x n in which a variety of healthy chocolates are present denoted by ‘H’ initially but he finds out that some of the chocolates are rotten and unhealthy denoted by ‘U’. In one day the rotten chocolates make all its neighboring chocolates unhealthy. This goes on and on until all chocolates present in the chocolate box become Unhealthy to eat. Find out the number of days in which the whole chocolate box becomes Unhealthy.
(Note: It is guaranteed that at least one of the chocolate is Unhealthy)
Examples:
Input : n = 3
H H H
H U H
H H H
Output : 1
Only 1 day is required to turn all the
chocolates unhealthy in the chocolate box.
Input : n = 4
H H H U
H H H H
H U H H
H H H H
Output : 2
Explanation:
In first day chocolate at (0, 0), (0, 1),
(2, 3), (3, 3) will remain healthy and in
the second day all the chocolates will
become unhealthy.
Asked in Amazon, Accolite, and Arcesium.
Brute Force Approach:
Initialize a flag = 1. Use a while loop, inside that while searching for an H (searching requires O(n^2) time complexity if we are unable to find an H in the 2-D character array stop incrementing the day counter and set the flag as 0 to break the loop.
Below is the implementation of the above approach:
C++
// CPP program to find number of days before// all chocolates become unhealthy.#include <bits/stdc++.h>using namespace std;// Validates out of bounds indexingbool isValid(int i, int j, int n){ if (i < 0 || j < 0 || i >= n || j >= n) return false; return true;}// function for returning number of daysint numdays(char arr[][4], int n){ int numdays = 0; while (true) { // Traverse matrix to look for unhealthy // chocolates and mark their neighbors. for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == 'U') { if (isValid(i - 1, j - 1, n) && arr[i - 1][j - 1] == 'H') arr[i - 1][j - 1] = 'V'; if (isValid(i - 1, j, n) && arr[i - 1][j] == 'H') arr[i - 1][j] = 'V'; if (isValid(i - 1, j + 1, n) && arr[i - 1][j + 1] == 'H') arr[i - 1][j + 1] = 'V'; if (isValid(i, j - 1, n) && arr[i][j - 1] == 'H') arr[i][j - 1] = 'V'; if (isValid(i, j + 1, n) && arr[i][j + 1] == 'H') arr[i][j + 1] = 'V'; if (isValid(i + 1, j - 1, n) && arr[i + 1][j - 1] == 'H') arr[i + 1][j - 1] = 'V'; if (isValid(i + 1, j, n) && arr[i + 1][j] == 'H') arr[i + 1][j] = 'V'; if (isValid(i + 1, j + 1, n) && arr[i + 1][j + 1] == 'H') arr[i + 1][j + 1] = 'V'; } /*Here we are assigning the neighbours of U with the character V because we don't want these neighbours to be counted in that particular day. If we do not do so, in the next iteration that neighbour will also get counted which was supposed to be counted in the next day. */ } } // Mark chocolates unhealthy which are made // unhealthy in current day. bool Hflag = false; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == 'V') { arr[i][j] = 'U'; Hflag = true; } } } // Check if there was any chocoloate // marked unhealthy in current day if (Hflag) numdays++; else break; } return numdays;}// Driver functionint main(){ int n = 4; char arr[4][4] = { 'H', 'H', 'H', 'U', 'H', 'H', 'H', 'H', 'H', 'U', 'H', 'H', 'H', 'H', 'H', 'H' }; int ans = numdays(arr, n); cout << "number of days taken : " << ans << "\n"; return 0;} |
C
// C program to find number of days before// all chocolates become unhealthy.#include <stdio.h>// Validates out of bounds indexingint isValid(int i, int j, int n){ if (i < 0 || j < 0 || i >= n || j >= n) return 0; return 1;}// function for returning number of daysint numdays(char arr[][4], int n){ int numdays = 0; while (1) { // Traverse matrix to look for unhealthy // chocolates and mark their neighbors. for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == 'U') { if (isValid(i - 1, j - 1, n) && arr[i - 1][j - 1] == 'H') arr[i - 1][j - 1] = 'V'; if (isValid(i - 1, j, n) && arr[i - 1][j] == 'H') arr[i - 1][j] = 'V'; if (isValid(i - 1, j + 1, n) && arr[i - 1][j + 1] == 'H') arr[i - 1][j + 1] = 'V'; if (isValid(i, j - 1, n) && arr[i][j - 1] == 'H') arr[i][j - 1] = 'V'; if (isValid(i, j + 1, n) && arr[i][j + 1] == 'H') arr[i][j + 1] = 'V'; if (isValid(i + 1, j - 1, n) && arr[i + 1][j - 1] == 'H') arr[i + 1][j - 1] = 'V'; if (isValid(i + 1, j, n) && arr[i + 1][j] == 'H') arr[i + 1][j] = 'V'; if (isValid(i + 1, j + 1, n) && arr[i + 1][j + 1] == 'H') arr[i + 1][j + 1] = 'V'; } /*Here we are assigning the neighbours of U with the character V because we don't want these neighbours to be counted in that particular day. If we do not do so, in the next iteration that neighbour will also get counted which was supposed to be counted in the next day. */ } } // Mark chocolates unhealthy which are made // unhealthy in current day. int Hflag = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == 'V') { arr[i][j] = 'U'; Hflag = 1; } } } // Check if there was any chocoloate // marked unhealthy in current day if (Hflag) numdays++; else break; } return numdays;}// Driver Codeint main(){ int n = 4; char arr[4][4] = { 'H', 'H', 'H', 'U', 'H', 'H', 'H', 'H', 'H', 'U', 'H', 'H', 'H', 'H', 'H', 'H' }; int ans = numdays(arr, n); printf("number of days taken : %d\n", ans); return 0;}// This code is contributed by ankush_953 |
Java
// Java program to find number of days before// all chocolates become unhealthy.class GFG{ // Validates out of bounds indexing static boolean isValid(int i, int j, int n) { if (i < 0 || j < 0 || i >= n || j >= n) return false; return true; } // function for returning number of days static int numdays(char [][]arr, int n) { int numdays = 0; while (true) { // Traverse matrix to look for unhealthy // chocolates and mark their neighbors. for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == 'U') { if (isValid(i - 1, j - 1, n) && arr[i - 1][j - 1] == 'H') arr[i - 1][j - 1] = 'V'; if (isValid(i - 1, j, n) && arr[i - 1][j] == 'H') arr[i - 1][j] = 'V'; if (isValid(i - 1, j + 1, n) && arr[i - 1][j + 1] == 'H') arr[i - 1][j + 1] = 'V'; if (isValid(i, j - 1, n) && arr[i][j - 1] == 'H') arr[i][j - 1] = 'V'; if (isValid(i, j + 1, n) && arr[i][j + 1] == 'H') arr[i][j + 1] = 'V'; if (isValid(i + 1, j - 1, n) && arr[i + 1][j - 1] == 'H') arr[i + 1][j - 1] = 'V'; if (isValid(i + 1, j, n) && arr[i + 1][j] == 'H') arr[i + 1][j] = 'V'; if (isValid(i + 1, j + 1, n) && arr[i + 1][j + 1] == 'H') arr[i + 1][j + 1] = 'V'; } /*Here we are assigning the neighbours of U with the character V because we don't want these neighbours to be counted in that particular day. If we do not do so, in the next iteration that neighbour will also get counted which was supposed to be counted in the next day. */ } } // Mark chocolates unhealthy which are made // unhealthy in current day. boolean Hflag = false; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == 'V') { arr[i][j] = 'U'; Hflag = true; } } } // Check if there was any chocoloate // marked unhealthy in current day if (Hflag) numdays++; else break; } return numdays; } // Driver Code public static void main(String []args) { int n = 4; char [][]arr = {{'H', 'H', 'H', 'U'}, {'H', 'H', 'H', 'H'}, {'H', 'U', 'H', 'H'}, {'H', 'H', 'H', 'H'}}; int ans = numdays(arr, n); System.out.println("number of days taken : " + ans); }}// This code is contributed by ankush_953 |
Python3
# Python3 program to find number of days before# all chocolates become unhealthy.# Validates out of bounds indexingdef isValid(i, j, n): if (i < 0 or j < 0 or i >= n or j >= n): return False return True# function for returning number of daysdef numdays(arr, n): numdays = 0 while (True): # Traverse matrix to look for unhealthy # chocolates and mark their neighbors. for i in range(n): for j in range(n): if (arr[i][j] == 'U'): if (isValid(i - 1, j - 1, n) and\ arr[i - 1][j - 1] == 'H'): arr[i - 1][j - 1] = 'V' if (isValid(i - 1, j, n) and\ arr[i - 1][j] == 'H'): arr[i - 1][j] = 'V' if (isValid(i - 1, j + 1, n) and\ arr[i - 1][j + 1] == 'H'): arr[i - 1][j + 1] = 'V' if (isValid(i, j - 1, n) and\ arr[i][j - 1] == 'H'): arr[i][j - 1] = 'V' if (isValid(i, j + 1, n) and\ arr[i][j + 1] == 'H'): arr[i][j + 1] = 'V' if (isValid(i + 1, j - 1, n) and\ arr[i + 1][j - 1] == 'H'): arr[i + 1][j - 1] = 'V' if (isValid(i + 1, j, n) and\ arr[i + 1][j] == 'H'): arr[i + 1][j] = 'V' if (isValid(i + 1, j + 1, n) and\ arr[i + 1][j + 1] == 'H'): arr[i + 1][j + 1] = 'V' # Here we are assigning the neighbours of U # with the character V because we don't want # these neighbours to be counted in that # particular day. If we do not do so, in the # next iteration that neighbour will also get # counted which was supposed to be counted in # the next day. # Mark chocolates unhealthy which are made # unhealthy in current day. Hflag = False for i in range(n): for j in range(n): if (arr[i][j] == 'V'): arr[i][j] = 'U' Hflag = True # Check if there was any chocoloate # marked unhealthy in current day if (Hflag): numdays += 1 else: break return numdays# Driver Coden = 4arr = [['H', 'H', 'H', 'U'], ['H', 'H', 'H', 'H'], ['H', 'U', 'H', 'H'], ['H', 'H', 'H', 'H']]ans = numdays(arr, n)print("number of days taken :", ans)# This code is contributed by ankush_953 |
C#
// C# program to find number of days before// all chocolates become unhealthy.using System;class GFG{ // Validates out of bounds indexing static bool isValid(int i, int j, int n) { if (i < 0 || j < 0 || i >= n || j >= n) return false; return true; } // function for returning number of days static int numdays(char[][] arr, int n) { int numdays = 0; while (true) { // Traverse matrix to look for unhealthy // chocolates and mark their neighbors. for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == 'U') { if (isValid(i - 1, j - 1, n) && arr[i - 1][j - 1] == 'H') arr[i - 1][j - 1] = 'V'; if (isValid(i - 1, j, n) && arr[i - 1][j] == 'H') arr[i - 1][j] = 'V'; if (isValid(i - 1, j + 1, n) && arr[i - 1][j + 1] == 'H') arr[i - 1][j + 1] = 'V'; if (isValid(i, j - 1, n) && arr[i][j - 1] == 'H') arr[i][j - 1] = 'V'; if (isValid(i, j + 1, n) && arr[i][j + 1] == 'H') arr[i][j + 1] = 'V'; if (isValid(i + 1, j - 1, n) && arr[i + 1][j - 1] == 'H') arr[i + 1][j - 1] = 'V'; if (isValid(i + 1, j, n) && arr[i + 1][j] == 'H') arr[i + 1][j] = 'V'; if (isValid(i + 1, j + 1, n) && arr[i + 1][j + 1] == 'H') arr[i + 1][j + 1] = 'V'; } /*Here we are assigning the neighbours of U with the character V because we don't want these neighbours to be counted in that particular day. If we do not do so, in the next iteration that neighbour will also get counted which was supposed to be counted in the next day. */ } } // Mark chocolates unhealthy which are made // unhealthy in current day. bool Hflag = false; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (arr[i][j] == 'V') { arr[i][j] = 'U'; Hflag = true; } } } // Check if there was any chocoloate // marked unhealthy in current day if (Hflag) numdays++; else break; } return numdays; } // Driver function static public void Main () { int n = 4; char[][] arr = new char[][]{"HHHU".ToCharArray(), "HHHH".ToCharArray(), "HUHH".ToCharArray(), "HHHH".ToCharArray()}; int ans = numdays(arr, n); Console.WriteLine("number of days taken : "+ ans); }}// This code is contributed by shubhamsingh10 |
Javascript
<script>// Python3 program to find number of days before// all chocolates become unhealthy.// Validates out of bounds indexingfunction isValid(i, j, n){ if (i < 0 || j < 0 || i >= n || j >= n) return false return true}// function for returning number of daysfunction numdays(arr, n){ let numdays = 0 while (true) { // Traverse matrix to look for unhealthy // chocolates and mark their neighbors. for(let i = 0; i < n; i++) { for(let j = 0; j < n; j++) { if (arr[i][j] == 'U') { if (isValid(i - 1, j - 1, n) && arr[i - 1][j - 1] == 'H') arr[i - 1][j - 1] = 'V' if (isValid(i - 1, j, n) && arr[i - 1][j] == 'H') arr[i - 1][j] = 'V' if (isValid(i - 1, j + 1, n) && arr[i - 1][j + 1] == 'H') arr[i - 1][j + 1] = 'V' if (isValid(i, j - 1, n) && arr[i][j - 1] == 'H') arr[i][j - 1] = 'V' if (isValid(i, j + 1, n) && arr[i][j + 1] == 'H') arr[i][j + 1] = 'V' if (isValid(i + 1, j - 1, n) && arr[i + 1][j - 1] == 'H') arr[i + 1][j - 1] = 'V' if (isValid(i + 1, j, n) && arr[i + 1][j] == 'H') arr[i + 1][j] = 'V' if (isValid(i + 1, j + 1, n) && arr[i + 1][j + 1] == 'H') arr[i + 1][j + 1] = 'V' } // Here we are assigning the neighbours of U // with the character V because we don't want // these neighbours to be counted in that // particular day. If we do not do so, in the // next iteration that neighbour will also get // counted which was supposed to be counted in // the next day. } } // Mark chocolates unhealthy which are made // unhealthy in current day. let Hflag = false for(let i=0;i<n;i++){ for(let j=0;j<n;j++){ if (arr[i][j] == 'V'){ arr[i][j] = 'U' Hflag = true } } } // Check if there was any chocoloate // marked unhealthy in current day if(Hflag) numdays++ else break } return numdays}// Driver Codelet n = 4let arr = [['H', 'H', 'H', 'U'], ['H', 'H', 'H', 'H'], ['H', 'U', 'H', 'H'], ['H', 'H', 'H', 'H']]let ans = numdays(arr, n)document.write("number of days taken : ", ans)// This code is contributed by shinjanpatra</script> |
Output
number of days taken : 2
Time Complexity: O(n2)
Auxiliary Space: O(1)
Efficient Approach (Uses BFS):
In this approach, declare a queue which inputs pairs that corresponds to the index of the unhealthy chocolates, and then as soon as the index (-1, -1) is reached we increment the numdays counter. This Solution is basically based on calculating levels in level order traversal (Iterative version) of a binary tree in which we push the initial indexes of the unhealthy chocolates instead of the root node and increment numdays instead of the level counter as soon as the index (-1, -1) is reached instead of NULL. As soon as the counter of the flag reaches 2 we break the loop denoting that queue has encountered two consecutive (-1, -1) pairs.
Below is the implementation of the above approach:
C++
// CPP program using Efficient approach// to find number of days#include <bits/stdc++.h>using namespace std;// Validates out of bounds indexingbool isValid(int i, int j, int n){ if (i < 0 || j < 0 || i >= n || j >= n) return false; return true;}// function for returning number of daysint numdays(char arr[][4], int n){ int numdays = 0; int i, j; queue<pair<int, int> > q; // Initializing queue with initial // positions of unhealthy chocolates for (i = 0; i < n; i++) for (j = 0; j < n; j++) { if (arr[i][j] == 'U') q.push(make_pair(i, j)); } q.push(make_pair(-1, -1)); // (-1, -1) is used as a checkpoint // to count the number of days pair<int, int> temp; // temporary pair to store the indexes int flag = 0; while (!q.empty()) { temp = q.front(); i = temp.first; j = temp.second; q.pop(); if (i == -1 && j == -1) { flag++; q.push(make_pair(-1, -1)); // pushing the respective // checkpoint if (flag == 2) break; numdays++; } else { flag = 0; if (isValid(i - 1, j - 1, n) && arr[i - 1][j - 1] == 'H') { q.push(make_pair(i - 1, j - 1)); arr[i - 1][j - 1] = 'U'; } if (isValid(i - 1, j, n) && arr[i - 1][j] == 'H') { q.push(make_pair(i - 1, j)); arr[i - 1][j] = 'U'; } if (isValid(i - 1, j + 1, n) && arr[i - 1][j + 1] == 'H') { q.push(make_pair(i - 1, j + 1)); arr[i - 1][j + 1] = 'U'; } if (isValid(i, j - 1, n) && arr[i][j - 1] == 'H') { q.push(make_pair(i, j - 1)); arr[i][j - 1] = 'U'; } if (isValid(i, j + 1, n) && arr[i][j + 1] == 'H') { q.push(make_pair(i, j + 1)); arr[i][j + 1] = 'U'; } if (isValid(i + 1, j - 1, n) && arr[i + 1][j - 1] == 'H') { q.push(make_pair(i + 1, j - 1)); arr[i + 1][j - 1] = 'U'; } if (isValid(i + 1, j, n) && arr[i + 1][j] == 'H') { q.push(make_pair(i + 1, j)); arr[i + 1][j] = 'U'; } if (isValid(i + 1, j + 1, n) && arr[i + 1][j + 1] == 'H') { q.push(make_pair(i + 1, j + 1)); arr[i + 1][j + 1] = 'U'; } } } return numdays - 1;}// Driver functionint main(){ int n = 4; char arr[4][4] = { 'H', 'H', 'H', 'U', 'H', 'H', 'H', 'H', 'H', 'H', 'U', 'H', 'H', 'H', 'H', 'H' }; int ans = numdays(arr, n); cout << "number of days taken : " << ans << "\n"; return 0;} |
Java
// Java program using Efficient approach// to find number of daysimport java.util.*;class gfg2 { static class pair { int first, second; pair(int f, int s) { first = f; second = s; } } // Validates out of bounds indexing static boolean isValid(int i, int j, int n) { if (i < 0 || j < 0 || i >= n || j >= n) return false; return true; } // function for returning number of days static int numdays(char arr[][], int n) { int numdays = 0; int i, j; Queue<pair> q = new ArrayDeque<>(); // Initializing queue with initial // positions of unhealthy chocolates for (i = 0; i < n; i++) for (j = 0; j < n; j++) { if (arr[i][j] == 'U') q.add(new pair(i, j)); } q.add(new pair(-1, -1)); // (-1, -1) is used as a checkpoint // to count the number of days pair temp; // temporary pair to store the indexes int flag = 0; while (!q.isEmpty()) { temp = q.peek(); i = temp.first; j = temp.second; q.remove(); if (i == -1 && j == -1) { flag++; q.add(new pair(-1, -1)); // pushing the respective // checkpoint if (flag == 2) break; numdays++; } else { flag = 0; if (isValid(i - 1, j - 1, n) && arr[i - 1][j - 1] == 'H') { q.add(new pair(i - 1, j - 1)); arr[i - 1][j - 1] = 'U'; } if (isValid(i - 1, j, n) && arr[i - 1][j] == 'H') { q.add(new pair(i - 1, j)); arr[i - 1][j] = 'U'; } if (isValid(i - 1, j + 1, n) && arr[i - 1][j + 1] == 'H') { q.add(new pair(i - 1, j + 1)); arr[i - 1][j + 1] = 'U'; } if (isValid(i, j - 1, n) && arr[i][j - 1] == 'H') { q.add(new pair(i, j - 1)); arr[i][j - 1] = 'U'; } if (isValid(i, j + 1, n) && arr[i][j + 1] == 'H') { q.add(new pair(i, j + 1)); arr[i][j + 1] = 'U'; } if (isValid(i + 1, j - 1, n) && arr[i + 1][j - 1] == 'H') { q.add(new pair(i + 1, j - 1)); arr[i + 1][j - 1] = 'U'; } if (isValid(i + 1, j, n) && arr[i + 1][j] == 'H') { q.add(new pair(i + 1, j)); arr[i + 1][j] = 'U'; } if (isValid(i + 1, j + 1, n) && arr[i + 1][j + 1] == 'H') { q.add(new pair(i + 1, j + 1)); arr[i + 1][j + 1] = 'U'; } } } return numdays - 1; } // Driver function public static void main(String[] args) { int n = 4; char arr[][] = { { 'H', 'H', 'H', 'U' }, { 'H', 'H', 'H', 'H' }, { 'H', 'H', 'U', 'H' }, { 'H', 'H', 'H', 'H' } }; int ans = numdays(arr, n); System.out.println("number of days taken : " + ans); }}// This code is contributed by karandeep1234 |
Python3
# Python3 program using Efficient approach# to find number of days# Validates out of bounds indexingdef isValid(i, j, n): if (i < 0 or j < 0 or i >= n or j >= n): return False return True# function for returning number of daysdef numdays(arr, n): numdays = 0 i = 0 j = 0 q = [] # Initializing queue with initial # positions of unhealthy chocolates for i in range(n): for j in range(n): if (arr[i][j] == 'U'): q.append([i, j]) q.append([-1, -1]) # (-1, -1) is used as a checkpo # to count the number of days temp = [] # temporary pair to store the indexes flag = 0 while (len(q)): temp = q[0] i = temp[0] j = temp[1] q.pop(0) if (i == -1 and j == -1): flag += 1 q.append([-1, -1]) # appending the respective # checkpo if (flag == 2): break numdays += 1 else: flag = 0 if (isValid(i - 1, j - 1, n) and arr[i - 1][j - 1] == 'H'): q.append([i - 1, j - 1]) arr[i - 1][j - 1] = 'U' if (isValid(i - 1, j, n) and arr[i - 1][j] == 'H'): q.append([i - 1, j]) arr[i - 1][j] = 'U' if (isValid(i - 1, j + 1, n) and arr[i - 1][j + 1] == 'H'): q.append([i - 1, j + 1]) arr[i - 1][j + 1] = 'U' if (isValid(i, j - 1, n) and arr[i][j - 1] == 'H'): q.append([i, j - 1]) arr[i][j - 1] = 'U' if (isValid(i, j + 1, n) and arr[i][j + 1] == 'H'): q.append([i, j + 1]) arr[i][j + 1] = 'U' if (isValid(i + 1, j - 1, n) and arr[i + 1][j - 1] == 'H'): q.append([i + 1, j - 1]) arr[i + 1][j - 1] = 'U' if (isValid(i + 1, j, n) and arr[i + 1][j] == 'H'): q.append([i + 1, j]) arr[i + 1][j] = 'U' if (isValid(i + 1, j + 1, n) and arr[i + 1][j + 1] == 'H'): q.append([i + 1, j + 1]) arr[i + 1][j + 1] = 'U' return numdays - 1# Driver functionn = 4arr = [['H', 'H', 'H', 'U'],['H', 'H', 'H', 'H'], ['H', 'H', 'U', 'H'],['H', 'H', 'H', 'H']] ans = numdays(arr, n)print("number of days taken :",ans)# This code is contributed by shubhamsingh10 |
C#
// C# program using Efficient approach// to find number of daysusing System;using System.Collections.Generic;class GFG{ // Validates out of bounds indexing static bool isValid(int i, int j, int n) { if (i < 0 || j < 0 || i >= n || j >= n) return false; return true; } // function for returning number of days static int numdays(char[, ] arr, int n) { int numdays = 0; int i, j; List< int[]> q = new List< int[]>(); // Initializing queue with initial // positions of unhealthy chocolates for (i = 0; i < n; i++) for (j = 0; j < n; j++) { if (arr[i, j] == 'U') q.Add(new int[] {i, j}); } q.Add(new int[] {-1, -1}); // (-1, -1) is used as a checkpoint // to count the number of days int[] temp = {-1, -1}; // temporary pair to store the indexes int flag = 0; while (q.Count > 0){ temp = q[0]; i = temp[0]; j = temp[1]; q.RemoveAt(0); if (i == -1 && j == -1) { flag++; q.Add(new int[] {-1, -1}); // Adding the respective // checkpoint if (flag == 2) break; numdays++; } else { flag = 0; if (isValid(i - 1, j - 1, n) && arr[i - 1, j - 1] == 'H') { q.Add(new int[] {i - 1, j - 1}); arr[i - 1, j - 1] = 'U'; } if (isValid(i - 1, j, n) && arr[i - 1, j] == 'H') { q.Add(new int[] {i - 1, j}); arr[i - 1, j] = 'U'; } if (isValid(i - 1, j + 1, n) && arr[i - 1, j + 1] == 'H') { q.Add(new int[] {i - 1, j + 1}); arr[i - 1, j + 1] = 'U'; } if (isValid(i, j - 1, n) && arr[i, j - 1] == 'H') { q.Add(new int[] {i, j - 1}); arr[i, j - 1] = 'U'; } if (isValid(i, j + 1, n) && arr[i, j + 1] == 'H') { q.Add(new int[] {i, j + 1}); arr[i, j + 1] = 'U'; } if (isValid(i + 1, j - 1, n) && arr[i + 1, j - 1] == 'H') { q.Add(new int[] {i + 1, j - 1}); arr[i + 1, j - 1] = 'U'; } if (isValid(i + 1, j, n) && arr[i + 1, j] == 'H') { q.Add(new int[] {i + 1, j}); arr[i + 1, j] = 'U'; } if (isValid(i + 1, j + 1, n) && arr[i + 1, j + 1] == 'H') { q.Add(new int[] {i + 1, j + 1}); arr[i + 1, j + 1] = 'U'; } } } return numdays - 1; } // Driver function public static void Main(string[] args) { int n = 4; char[,] arr = { {'H', 'H', 'H', 'U'}, {'H', 'H', 'H', 'H'}, {'H', 'H', 'U', 'H'}, {'H', 'H', 'H', 'H' }}; int ans = numdays(arr, n); Console.Write("number of days taken : " + ans); }}// This code is contributed by phasing17. |
Javascript
<script>// JavaScript program using Efficient approach// to find number of days// Validates out of bounds indexingfunction isValid(i, j, n){ if (i < 0 || j < 0 || i >= n || j >= n) return false return true}// function for returning number of daysfunction numdays(arr, n){ let numdays = 0 let i = 0 let j = 0 let q = [] // Initializing queue with initial // positions of unhealthy chocolates for(let i=0;i<n;i++){ for(let j=0;j<n;j++){ if (arr[i][j] == 'U'){ q.push([i, j]) } } } q.push([-1, -1]) // (-1, -1) is used as a checkpo // to count the number of days let temp = [] // temporary pair to store the indexes let flag = 0 while (q.length){ let temp = q.shift() let i = temp[0] let j = temp[1] if (i == -1 && j == -1){ flag += 1 q.push([-1, -1]) // pushing the respective // checkpo if (flag == 2) break numdays += 1 } else{ flag = 0 if (isValid(i - 1, j - 1, n) && arr[i - 1][j - 1] == 'H'){ q.push([i - 1, j - 1]) arr[i - 1][j - 1] = 'U' } if (isValid(i - 1, j, n) && arr[i - 1][j] == 'H'){ q.push([i - 1, j]) arr[i - 1][j] = 'U' } if (isValid(i - 1, j + 1, n) && arr[i - 1][j + 1] == 'H'){ q.push([i - 1, j + 1]) arr[i - 1][j + 1] = 'U' } if (isValid(i, j - 1, n) && arr[i][j - 1] == 'H'){ q.push([i, j - 1]) arr[i][j - 1] = 'U' } if (isValid(i, j + 1, n) && arr[i][j + 1] == 'H'){ q.push([i, j + 1]) arr[i][j + 1] = 'U' } if (isValid(i + 1, j - 1, n) && arr[i + 1][j - 1] == 'H'){ q.push([i + 1, j - 1]) arr[i + 1][j - 1] = 'U' } if (isValid(i + 1, j, n) && arr[i + 1][j] == 'H'){ q.push([i + 1, j]) arr[i + 1][j] = 'U' } if (isValid(i + 1, j + 1, n) && arr[i + 1][j + 1] == 'H'){ q.push([i + 1, j + 1]) arr[i + 1][j + 1] = 'U' } } } return numdays - 1}// Driver functionlet n = 4let arr = [['H', 'H', 'H', 'U'],['H', 'H', 'H', 'H'], ['H', 'H', 'U', 'H'],['H', 'H', 'H', 'H']] let ans = numdays(arr, n)document.write("number of days taken :",ans,"</br>")// This code is contributed by shinjanpatra</script> |
Output
number of days taken : 2
Time Complexity: O(n2)
Auxiliary Space: O(n2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
