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 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

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

Welcome to Java! Hackerrank Solution in Java

By
  W elcome to Java! Hackerrank Solution in Java Problem-1:- Welcome to the world of Java! In this challenge, we practice printing to stdout. The code stubs in your editor declare a  Solution  class and a  main  method. Complete the  main  method by copying the two lines of code below and pasting them inside the body of your  main  method. System . out . println ( "Hello, World." ); System . out . println ( "Hello, Java." ); Input Format There is no input for this challenge. Output Format You must print two lines of output: Print  Hello, World.  on the first line. Print  Hello, Java.  on the second line. Sample Output Hello, World. Hello, Java. Solution:- public   class   Solution   {      public   static   void   main ( String []   args )   {          /* Enter your code here. Print output...
Post a Comment
Read more