Skip to main content

Flood Fill

 1. You are given a number n, representing the number of rows.

2. You are given a number m, representing the number of columns.

3. You are given n*m numbers, representing elements of 2d array a. The numbers can be 1 or 0 only.

4. You are standing in the top-left corner and have to reach the bottom-right corner. 

Only four moves are allowed 't' (1-step up), 'l' (1-step left), 'd' (1-step down) 'r' (1-step right). You can only move to cells which have 0 value in them. You can't move out of the boundaries or in the cells which have value 1 in them (1 means obstacle)

5. Complete the body of floodfill function - without changing signature - to print all paths that can be used to move from top-left to bottom-right.


Note1 -> Please check the sample input and output for details

Note2 -> If all four moves are available make moves in the order 't', 'l', 'd' and 'r'

Input Format

A number n

A number m

e11

e12..

e21

e22..

.. n * m number of elements

Output Format

trrrdlt

tlldrt

.. and so on


Constraints

1 <= n <= 10

1 <= m <= 10

e1, e2, .. n * m elements belongs to set (0, 1)

Sample Input

3 3

0 0 0

1 0 1

0 0 0

Sample Output

rddr


Solution:

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        int m = scn.nextInt();
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = scn.nextInt();
            }
        }
        boolean visited[][] = new boolean[n][m];
        floodfill(arr, 0, 0, "", visited);
    }
    
    // asf -> answer so far
    public static void floodfill(int[][] maze, int sr, int sc, String asf, boolean visited[][]) {
        if(sr<0 || sc<0 || (sr==maze.length) || sc==maze[0].length || maze[sr][sc] == 1 || visited[sr][sc] == true) return;
        if(sr == (maze.length-1) && sc == (maze[0].length-1)){
            System.out.println(asf);
            return;
        }
        visited[sr][sc] = true;
        floodfill(maze,sr-1,sc,asf+"t",visited);
        floodfill(maze,sr,sc-1,asf+"l",visited);
        floodfill(maze,sr+1,sc,asf+"d",visited);
        floodfill(maze,sr,sc+1,asf+"r",visited);
        visited[sr][sc] = false;
    }
}

Comments

Popular posts from this blog

Classes and Objects | Accenture TFA

  Question  1 Correct Mark 1.00 out of 1.00 Flag question Question text ___ and _____ are the access specifiers that can be applied to top level Class. Select one or more: public   protected default   private Feedback Your answer is correct. The correct answers are: default, public Question  2 Correct Mark 1.00 out of 1.00 Flag question Question text class Sample{      private double num = 100;    private int square(int a){ return a*a;    } }   public class Test{    public static void main(String args[]){   Sample obj = new Sample();   System.out.println(obj.num);  System.out.println(obj.square(10));    }   } Select one: Compile time error   Run time error Executes but no output 100 Feedback Your answer is correct. The correct answer is: Compile time error Question  3 Correct Mark 1.00 out of 1.00 Flag question Question text Choose the appropriate access specifier for the attribute value so that it can be accessed from anywhere. class Test { Choose... private protected public d

Classes and Objects, Packages | Accenture TFA

  Question  1 Correct Mark 1.00 out of 1.00 Flag question Question text State True or False When using eclipse whichever classes are needed for the present class can be imported automatically. Select one: True   False Feedback The correct answer is 'True'. Question  2 Correct Mark 1.00 out of 1.00 Flag question Question text switch(a) {     default:         System.out.println("Welcome"); } Of which data types can the variable ‘a’ be? 1. long 2. byte 3. int 4. char 5. float 6. short Select one: 3, 4 and 5 1 and 3 3 and 4 2,3, 4 and 6   Feedback Your answer is correct. The variable used in a switch statement can be a byte, short, int, char or String type only. The correct answer is:  2,3, 4 and 6 Question  3 Correct Mark 1.00 out of 1.00 Flag question Question text Predict the output.   public class Test {         public static void main(String args[])         {                     int a = 2, b = 0;              for ( ; b < 20; ++b) {                  if (b % a == 0)

Minimum Lights to Activate | Interview

Problem: Description There is a corridor in a Jail which is N units long. Given an array A of size N . The i th index of this array is 0 if the light at i th position is faulty otherwise it is 1. All the lights are of specific power B which if is placed at position X , it can light the corridor from [ X-B+1, X+B-1] . Initially all lights are off. Return the minimum number of lights to be turned ON to light the whole corridor or -1 if the whole corridor cannot be lighted. Problem Constraints 1 <= N <= 1000 1 <= B <= 1000 Input Format First argument is an integer array A where A[i] is either 0 or 1. Second argument is an integer B. Output Format Return the minimum number of lights to be turned ON to light the whole corridor or -1 if the whole corridor cannot be lighted. Example Input Input 1: A = [ 0, 0, 1, 1, 1, 0, 0, 1]. B = 3 Input 2: A = [ 0, 0, 0, 1, 0]. B = 3 Example Output Output 1: 2 Output 2: -1 Example Explanation Explanation 1: In the first configuration,