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

Java Output Formating Hackerrank Solution in Java

By
  Java Output Formating Hackerrank Solution in Java Problem-5:- Java's  System.out.printf  function can be used to print formatted output. The purpose of this exercise is to test your understanding of formatting output using  printf . To get you started, a portion of the solution is provided for you in the editor; you must format and print the input to complete the solution. Input Format Every line of input will contain a  String  followed by an  integer . Each  String  will have a maximum of   alphabetic characters, and each  integer  will be in the inclusive range from   to  . Output Format In each line of output there should be two columns: The first column contains the  String  and is left justified using exactly   characters. The second column contains the  integer , expressed in exactly   digits; if the original input has less than three digits, you must pad your outp...
Post a Comment
Read more

Java Stdin and Stdout II Hackerrank Solution in Java

By
 Java Stdin and Stdout II Hackerrank Solution in Java Problem-4:- In this challenge, you must read an  integer , a  double , and a  String  from stdin, then print the values according to the instructions in the  Output Format  section below. To make the problem a little easier, a portion of the code is provided for you in the editor. Note:  We recommend completing  Java Stdin and Stdout I  before attempting this challenge. Input Format There are three lines of input: The first line contains an  integer . The second line contains a  double . The third line contains a  String . Output Format There are three lines of output: On the first line, print  String:  followed by the unaltered  String  read from stdin. On the second line, print  Double:  followed by the unaltered  double  read from stdin. On the third line, print  Int:  followed by the unaltered  integer  rea...
Post a Comment
Read more

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