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

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

Benefits and Drawback of Being Alone!

By
 BENEFITS and DRAWBACK of BEING ALONE! Its been almost a month for me to live on my own. I am here writing my thoughts and things I have seen these couple of weeks not everything but I'll try to keep it subtle. I have some friends here and at least I think that. There are some pros and cons of everything. BENEFITS OF LIVING ALONE 1. Personal alone time:- Most of us find this hard in our daily life. But it gets easier when you live alone. In this time, you can do anything you like reading a book, exercising, meditation or anything you like. Slowly, you will learn about the things and habits you like and the things you don't like. 2. Getting active, not lazy:-   When we are at home we build a habit not to work and it becomes harder to do daily works even for ourselves. Here you can cook on your own, make the bed and most importantly clean. Because you know that no one is going to do that for you. 3. Managing your expenses:- I belong to a middle-class family and they have set a b...
Post a Comment
Read more