Skip to main content

Geek's Village and Well GFG solution in JAVA

Image
By

 Geek's Village and Well

Geek's village is represented by a 2-D matrix of characters of size n*m, where H - Represents a house W - Represents a well .- Represents open ground N - Prohibited area (Not allowed to enter in this area) Every house in the village needs to take the water from the well, as the family members are so busy with their work, so every family wants to take the water from the well in minimum time, which is possible only if they have to cover as less distance as possible. Your task is to determine the minimum distance that a person in the house should travel to take out the water and carry it back to the house.

A person is allowed to move only in four directions left, right, up, and down. That means if he/she is the cell (ij), then the possible cells he/she can reach in one move are (i,j-1), (i,j+1),(i-1.j),(i+1,j), and the person is not allowed to move out of the grid. 

Note: For all the cells containing 'N', 'W', and '.' our answer should be 0, and for all the houses where there is no possibility of taking water our answer should be -1. 
gfg example


SOLUTION:

//User function Template for Java
class Pair{
    int first, second;
    
    Pair(int f, int s){
        this.first = f;
        this.second = s;
    }
}

class Solution
{
    public int[][] chefAndWells(int n,int m,char grid[][])
    {
        int[][] ans = new int[n][m];
        
        Queue<Pair> q = new LinkedList<>();
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                
                if(grid[i][j] == 'W'){
                    ans[i][j] = 0;
                    q.add(new Pair(i, j));
                }
                else{
                    ans[i][j] = n*m+1;
                }
            }
        }
        
        int[] drow = {-1, 0, 1, 0};
        int[] dcol = {0, 1, 0, -1};
        
        while(!q.isEmpty()){
            
            Pair p = q.poll();
            int row = p.first;
            int col = p.second;
            
            for(int i = 0; i < 4; i++){
                
                int nrow = row + drow[i];
                int ncol = col + dcol[i];
                
                if(nrow >= 0 && ncol >= 0 && nrow < n && ncol < m && 
                    grid[nrow][ncol] != 'N' && ans[nrow][ncol] > ans[row][col] + 1){
                        ans[nrow][ncol] = ans[row][col] + 1;
                        q.add(new Pair(nrow, ncol));
                    }
            }
        }
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                
                if(grid[i][j] == 'H' && ans[i][j] == (n*m+1)){
                    ans[i][j] = -1;
                }else if(grid[i][j] != 'H'){
                    ans[i][j] = 0;
                }else{
                    ans[i][j] *= 2;
                }
            }
        }
        
        return ans;
    }
}

OUTPUT: 

Output


This question is of GFG Weekly Interview Series - 72. And the above approach is my approach that may help you. I HOPE, IT HELPS! 


Comments

Post a Comment

Popular posts from this blog

GOD! a Thought, a Helping hand, or a Myth? (Hindi & English)

By
  GOD! a Thought, a Helping hand, or a Myth? Hello friends! Today we are going to talk about God. Do you think God is a thought, a helping hand or a myth?  When we talk about God, in our knowledge he is our master who knows everything and can do everything. They help us, relieve us from our troubles and also improve our health. According to the experiences of many of his devotees, God is very important in our life and helps us with our problems.   हेलो दोस्तों! आज हम बात करने वाले हैं भगवान के बारे में। क्या आपको लगता है कि भगवान एक सोच, एक मददगार हाथ या एक मिथक है? मैंने अपने जीवन में भगवान से बहुत से लोगों को मिला है, और उनमें से हर एक का भगवान के बारे में अलग-अलग विचार है। कुछ लोग मानते हैं कि भगवान एक सोच है, जिसकी मदद से हम अपनी जिंदगी में सुधार ला सकते हैं। अन्य लोग मानते हैं कि भगवान एक मददगार हाथ है, जो हमारी समस्याओं को हल करने में हमारी मदद करता है। हालांकि, कुछ लोग मानते हैं कि भगवान एक मिथक है, जो केवल हमारी मनोबल को बढ़ाने के लिए ही है।     Often w...
Post a Comment
Read more

Utkarsh and Placement tests Codechef solution in Java, C++ || UTKPLC || December long challenge 2021

By
 Utkarsh and Placement tests Codechef solution in Java, C++ Note: Hope it helps you! Please note that all the intentions are to clear the doubt of how to solve it in java. So, please try to give it a chance at least before using this. If you face any discrepancy please contact us. Thank you! Utkarsh is currently sitting for placements. He has applied to three companies named  A , B,    and  C . You know Utkarsh's order of preference among these  3 3  companies, given to you as characters  first ,  second , and  third  respectively (where  first  is the company he prefers most). You also know that Utkarsh has received offers from exactly two of these three companies, given you as characters  x x  and  y y . Utkarsh will always accept the offer from whichever company is highest on his preference list. Which company will he join? Input Format The first line of input contains a single integer  T T , denotin...
1 comment
Read more

Java If-Else Hackkerrank Solution in Java

By
  J ava If-Else Hackkerrank Solution in Java Problem-3:- In this challenge, we test your knowledge of using  if-else  conditional statements to automate decision-making processes. An if-else statement has the following logical flow: Source:  Wikipedia Task Given an integer,  , perform the following conditional actions: If   is odd, print  Weird If   is even and in the inclusive range of   to  , print  Not Weird If   is even and in the inclusive range of   to  , print  Weird If   is even and greater than  , print  Not Weird Complete the stub code provided in your editor to print whether or not   is weird. Input Format A single line containing a positive integer,  . Constraints Output Format Print  Weird  if the number is weird; otherwise, print  Not Weird . Sample Input 0 3 Sample Output 0 Weird Sample Input 1 24 Sample Output 1 Not Weird E...
2 comments
Read more