Nitin Agrawal
Contact -
  • Home
  • Interviews
    • Secret Receipe
    • InterviewFacts
    • Resume Thoughts
    • Daily Coding Problems
    • BigShyft
    • Companies
    • Interviews Theory
  • Programming Languages
    • Java Script >
      • Tutorials
      • Code Snippets
    • Reactive Programming >
      • Code Snippets
    • R
    • DataStructures >
      • LeetCode Problems >
        • Problem10
        • Problem300
      • AnagramsSet
    • Core Java >
      • Codility
      • Program Arguments OR VM arguments & Environment variables
      • Java Releases >
        • Java8 >
          • Performance
          • NasHorn
          • WordCount
          • Thoughts
        • Java9 >
          • ServiceLoaders
          • Lambdas
          • List Of Objects
          • Code Snippets
        • Java14 >
          • Teeing
          • Pattern
          • Semaphores
        • Java17 >
          • Switches
          • FunctionalStreams
          • Predicate
          • Consumer_Supplier
          • Collectors in Java
        • Java21 >
          • Un-named Class
          • Virtual Threads
          • Structured Concurrency
      • Threading >
        • ThreadsOrder
        • ProducerConsumer
        • Finalizer
        • RaceCondition
        • Executors
        • Future Or CompletableFuture
      • Important Points
      • Immutability
      • Dictionary
      • Sample Code Part 1 >
        • PatternLength
        • Serialization >
          • Kryo2
          • JAXB/XSD
          • XStream
        • MongoDB
        • Strings >
          • Reverse the String
          • Reverse the String in n/2 complexity
          • StringEditor
          • Reversing String
          • String Puzzle
          • Knuth Morris Pratt
          • Unique characters
          • Top N most occurring characters
          • Longest Common Subsequence
          • Longest Common Substring
        • New methods in Collections
        • MethodReferences
        • Complex Objects Comparator >
          • Performance
        • NIO >
          • NIO 2nd Sample
        • Date Converter
        • Minimum cost path
        • Find File
      • URL Validator
    • Julia
    • Python >
      • Decorators
      • String Formatting
      • Generators_Threads
      • JustLikeThat
    • Go >
      • Tutorial
      • CodeSnippet
      • Go Routine_Channel
      • Suggestions
    • Methodologies & Design Patterns >
      • Design Principles
      • Design Patterns >
        • TemplatePattern
        • Adapter Design Pattern
        • Proxy
        • Lazy Initialization
        • CombinatorPattern
        • Singleton >
          • Singletons
        • Strategy
  • Frameworks
    • Apache Velocity
    • React Library >
      • Tutorial
    • Spring >
      • Spring Boot >
        • CustomProperties
        • ExceptionHandling
        • Custom Beans
        • Issues
      • Quick View
    • Rest WebServices >
      • Interviews
      • Swagger
    • Cloudera BigData >
      • Ques_Ans
      • Hive
      • Apache Spark >
        • ApacheSpark Installation
        • SparkCode
        • Sample1
        • DataFrames
        • RDDs
        • SparkStreaming
        • SparkFiles
    • Integration >
      • Apache Camel
    • Testing Frameworks >
      • JUnit >
        • JUnit Runners
      • EasyMock
      • Mockito >
        • Page 2
      • TestNG
    • Blockchain >
      • Ethereum Smart Contract
      • Blockchain Java Example
    • Microservices >
      • Messaging Formats
      • Design Patterns
    • AWS >
      • Honeycode
    • Dockers >
      • GitBash
      • Issues
      • Kubernetes
  • Databases
    • MySql
    • Oracle >
      • Interview1
      • SQL Queries
    • Elastic Search
  • Random issues
    • TOAD issue
    • Architect's suggestions
  • Your Views

​EscapeRooms

Problem Statement:
The EscapeRooms game consists of a grid ‘play’ representing a house of m * n size (m rows and n columns) where each cell represents a room. The grid is randomly generated with values 0 and -1. Now, you need to find out the total number of different possible paths to travel from the top left to the bottom right of this grid. Avoid backtracking – you can only move one step right or one step down.

There are certain rules to play this game:
1. To reach a cell with coordinates (m-1,n-1) a player can only start from the top left (0, 0) of the grid.
2. The player can only move one step right or one step down of the grid. This means that if he is currently at [0, 1] cell, he can move to either [0, 2] or [1, 1] room only 

3. There are few random cells in the grid with value -1 representing rooms that are locked via which no player can pass and remaining cells have value 0.
The number of locked rooms is indicated by a positive integer p and their positions are provided in a positive integer array numbers of size p * 2 such that the positions are to be read in pair. The locked rooms will have value -1.
figure,  
p=2,
numbers[4] = {1, 0, 2, 1}
which means in the grid play[3][3], 2 rooms are locked and their positions are play[1][0] and play[2][1] wherein first pair of the array numbers is [1,0] and 2nd pair is [2,1].

We need to count the number of paths a player can take to travel from [0,0] to [m-1, n-1].
public class EscapeRooms {

public static void main(String[] args) {
/*
* Case 1;
*/
int m = 5;
int n = 4;
int p = 4;
int[] numbers = {1,1,2,2,3,0,4,2};
// Ans : 3
/*
* Case 2
int m = 4;
int n = 3;
int p = 2;
int[] numbers = {2,0,2,2};
// Ans : 2
*/
/*
* Case 3
int m = 10;
int n = 5;
int p = 5;
int[] numbers = {2, 4, 3, 1, 6, 2, 8, 1, 9, 3};
// Ans : 179
*/
/*
* Case 4
int m = 2;
int n = 2;
int p = 1;
int[] numbers = {0, 1};
// Ans : 1
*/
long start = System.currentTimeMillis();
System.out.println(findPaths(m, n, p, numbers));
System.out.println("Time taken : " + (System.currentTimeMillis() - start) + " ms");
}

public static int findPaths(int m, int n, int p, int[] numbers) {

int[][] rooms = new int[m][n];
int i = 0;
while(p > 0) {
rooms[numbers[i]][numbers[i+1]] = -1;
i = i+2;
p--;
}

int count = totalPaths(m-1, n-1, rooms);
return count;
}

public static int totalPaths(int m, int n, int[][] rooms) {

int no = 0;
if(m == 0 && n == 0) {
return 1;
}
if(m == 0 && n > 0 && rooms[m][n] == 0) {
no = totalPaths(m, n-1, rooms);
} else if(m > 0 && n == 0 && rooms[m][n] == 0) {
no = totalPaths(m-1, n, rooms);
} else if(rooms[m][n] == 0){
int no1 = totalPaths(m-1, n, rooms);
int no2 = totalPaths(m, n-1, rooms);
no = no1 + no2;
}
if(rooms[m][n] == 0)
rooms[m][n] = no;
else if(rooms[m][n] > 0)
no = rooms[m][n];
return no;
}

}
Powered by Create your own unique website with customizable templates.