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

C program to print all repeated elements in an array and also print the count of repeated numbers

By
  Write a program to print all repeated elements in an array and also print the count of repeated numbers 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! Example: input: Enter the number of element: 4 Enter Elements: 10 20 10 20 output: The duplicate number is: 10 The duplicate number is: 20 The total number of the duplicate element is: 2 Algorithm of this program: Initially, we define the size of the array. Then, take a user-input size of the array and scan the element of the array. For finding the duplicate number in the array we have to run two for loops. The first for loop scan all elements from 0 index The next for loops run from i+1 so that it checks all the duplicate elements. If any duplicate element is found, we print the duplicate number and count it. At last, we print the count of ...
4 comments
Read more

Morning habits which can ruin your whole day

By
10 Bad Morning Habits Do you know the thing on which our whole day depends? If you think that this is morning, then you are absolutely right my friend. Our whole day depends on what we eat at breakfast, which time we wake up and what is the first thing we do when we woke up. 1. Snoozing your alarm:-   When you are going to sleep, that time you are fully determined that you woke up at 6:00 or 7:00am and you set up two or more alarm continuously with the break of 2 or 5 minutes. But in the morning, what happens? You start snoozing the alarm and doing this until you are late for your work. That time you have only one way to go to your work at the time is that you should skip your breakfast. Is it good? Absolutely not.  2.  Checking your message or E-mail just after you wake up 3. Drinking Coffee 4.  Not making your Bed 5. Eating Sugar for Breakfast:- 6. Leaving the Curtains closed:- 7. Not doing the Excercise 8. Doing ...
Post a Comment
Read more