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 Datatypes Hackerrank solution in Java

By
 Java Datatypes Hackerrank solution in Java Problem-7:- Java has 8 primitive data types;  char, boolean, byte, short, int, long, float, and double . For this exercise, we'll work with the primitives used to hold integer values ( byte, short, int,  and  long ): A  byte  is an 8-bit signed integer. A  short  is a 16-bit signed integer. An  int  is a 32-bit signed integer. A  long  is a 64-bit signed integer. Given an input integer, you must determine which primitive data types are capable of properly storing that input. To get you started, a portion of the solution is provided for you in the editor. Reference:   https://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html Input Format The first line contains an integer,  , denoting the number of test cases. Each test case,  , is comprised of a single line with an integer,  , which can be arbitrarily large or small. Output Format For each input variable   and appropriate primitive  , you must determine if the given primiti
1 comment
Read more

(Hindi/English) Remove Youtube, and other platform ads for free (Without subscription)

By
Hello friends, In today's digital world there is hardly anyone who does not use the Internet. If whenever a man learns to run the Internet, he first opens three things - YouTube Google Facebook That is why there are more than 50,000 searches on Google every second, while videos of more than 300 hours are uploaded to YouTube every minute. Now that so many people will come here every second, this will be the place to advertise for the best business. Because of this, we have to watch many ads, which are very annoying and boring but still, we have to watch. Or we get a notification to subscribe, which a common man cannot give in exchange for not just watching ads. So if you too are going through this problem then today this post is for you only. Today I have brought a website that will remove your problem. With this, not only YouTube but if you search any site on Google Chrome, then you will not have to bother with Ads. Let us start - You can watch the above video as
3 comments
Read more

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 output's leading digits with zeroes. Sample Input java 100 cpp 65 python 50 Sample Output ====================
Post a Comment
Read more