2
\$\begingroup\$

I have a functional backtracking solution, but I am only able to finish 22/25 test cases before exceeding my specified time limit. Any suggestions on how to improve the speed are greatly appreciated!

Note: I tried splitting method solve() into solveBinary() and solveDecimal() to remove repeated condition checks for 0 or 1, but it had no apparent effect and they are written the same.

Prompt

The map is full of 1s and 0s. For each set of starting and ending xy coordinates, determine if the destination can be reached using only 1s, only 0s, or neither (if start is 0 and end is 1, or vice versa, answer is neither)). North, south, east, west movements allowed.

//package kattis2people;

import java.util.Scanner;

public class Kattis2People {

    // map[][] will be full of 1s and 0s, traversed[][] initially contains all 0s.
    static int[][] map, traversed;

    // array of solutions to be printed at the end.
    static int[] solution;

    // dimensions of the map array.
    static int r, c;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        r = input.nextInt();
        c = input.nextInt();

        map = new int[r][c];

        // Fill the map array with given 1s and 0s.
        for (int i = 0; i < r; i++){
            input.nextLine();
            String row = input.next();
            for (int j = 0; j < c; j++){
                map[i][j] = row.charAt(j) - 48; //convert char '0' to int 0, char '1' to int 1
            }
        }

        input.nextLine();

        // number of traversal attempts forthcoming
        int numQueries = input.nextInt();

        solution = new int[numQueries];

        // for each traversal to be attempted, read in the source and the destination.
        for (int i = 0; i < numQueries; i++){
            input.nextLine();
            int r1 = input.nextInt() - 1; // input is 1-indexed, subtracting 1 to make it 0-indexed.
            int c1 = input.nextInt() - 1;
            int r2 = input.nextInt() - 1;
            int c2 = input.nextInt() - 1;

            // solve1() does premilinay work before calling solve() recursively.
            solution[i] = solve1(r1,c1,r2,c2, map[r1][c1]);
        }

        // print all solutions
        for (int i = 0; i < numQueries; i++){
            switch (solution[i]) {
                case -1:
                    System.out.println("neither");
                    break;
                case 0:
                    System.out.println("binary");
                    break;
                default:
                    System.out.println("decimal");
                    break;
            }
        }
    }


    private static int solve1(int r1, int c1, int r2, int c2, int x) {

        // if the source and destination don't use the same number system, there is no traversal possible.
        if (x != map[r2][c2])
            return -1;

        // keeps track of where we've been
        traversed = new int[r][c];

        // if the traversal is possible
        boolean result;

        if (x == 0)
            return (solveBinary(map, r1,c1,r2,c2)) ? 0 : -1; // successful traversal of 0s in map[][] returns 0
        else 
            return (solveDecimal(map, r1,c1,r2,c2)) ? 1 : -1; // traversal of 1s in map[][] returns 1
    }

    // recursively traverses 0s on the map[][[]
    private static boolean solveBinary(int[][]trial, int x1, int y1, int x2, int y2) {

        // we've reached the destination!
        if ((x1 == x2) && (y1 == y2)){
            traversed[x1][y1] = 1;
            return true;
        }

        // check if this is a valid move.
        if ((x1 >= 0 && x1 < r) && (y1 >= 0 && y1 < c) && (trial[x1][y1] == 0) && traversed[x1][y1] == 0){

            //if valid mark as traversed
            traversed[x1][y1] = 1;

            //try going furthur
            if (solveBinary(trial, x1+1, y1, x2, y2))
                return true;
            if (solveBinary(trial, x1-1, y1, x2, y2))
                return true;
            if (solveBinary(trial, x1, y1+1, x2, y2))
                return true; 
            if (solveBinary(trial, x1, y1-1, x2, y2))
                return true;
            traversed[x1][y1] = 1;
            return false;
        }
        return false;
    }

        // recursively traverse 1s on the map[][]
        private static boolean solveDecimal(int[][]trial, int x1, int y1, int x2, int y2) {

        // we've reached the destination!
        if ((x1 == x2) && (y1 == y2)){
            traversed[x1][y1] = 1;
            return true;
        }

        // check if this is a valid move.
        if ((x1 >= 0 && x1 < r) && (y1 >= 0 && y1 < c) && (trial[x1][y1] == 1) && traversed[x1][y1] == 0){

            //if valid mark as traversed
            traversed[x1][y1] = 1;

            //try going furthur
            if (solveDecimal(trial, x1+1, y1, x2, y2))
                return true;
            if (solveDecimal(trial, x1-1, y1, x2, y2))
                return true;
            if (solveDecimal(trial, x1, y1+1, x2, y2))
                return true; 
            if (solveDecimal(trial, x1, y1-1, x2, y2))
                return true;
            traversed[x1][y1] = 1;
            return false;
        }
        return false;
    } 
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You might want to add a heuristic that determines which direction is taken first (see for example A* algorithm). This probably saves a lot of backtracking steps \$\endgroup\$ – RobAu Feb 9 '18 at 9:20
1
\$\begingroup\$

Backtracking seems to be a bad choice for this particular problem.
A better solution can be implemented using Disjoint-set data structure.
Here is the algorithm,

create a disjoint-set for decimal people [people with 1 number assigned]
create a disjoint-set for binary people [people with 0 number assigned]

//if mat[][] is 2D matrix, storing content of the map (0's and 1's)

for(i in rows)
   for(j in columns)
       if(mat[i][j] == 1) {
          if(mat[i-1][j] == 1)                               //check all four direction of possible movement
                decimal.union(person(i,j), person(i-1,j));   // here person(i,j) is position of ith row, jth column person in disjoint-set
          if(mat[i][j-1] == 1) 
                decimal.union(person(i,j), person(i,j-1));
          if(mat[i+1][j] == 1) 
                decimal.union(person(i,j), person(i+1,j));
          if(mat[i][j+1] == 1) 
                decimal.union(person(i,j), person(i,j+1));
       }
       else { 
          if(mat[i-1][j] == 0) 
                binary.union(person(i,j), person(i-1,j));
          if(mat[i][j-1] == 0) 
                binary.union(person(i,j), person(i,j-1));
          if(mat[i+1][j] == 0) 
                binary.union(person(i,j), person(i+1,j));
          if(mat[i][j+1] == 0) 
                binary.union(person(i,j), person(i,j+1));
          }


//for executing query you just need to check if the two persons are in the same set or not
//let (x1,y1), (x2,y2) be the two points from the query input

if( binary.set(person(x1,y1)) == binary.set(person(x2,y2)) )
    print "binary"
else if( decimal.set(person(x1,y1)) == decimal.set(person(x2,y2)) )
    print "decimal"
else
    print "neither"

Here is the complete solution, implemented in Java. I also tried to run my implemented solution on the platform linked, It turn out to give Accepted status with running time 0.46s :)

import java.io.*;

class DisjointSet {

   int[] set = null;
   int[] rank = null;

   DisjointSet(int n) {

      set = new int[n];
      rank = new int[n];

      for(int i=0; i<n; i++){
         rank[i] = 0;
         set[i] = i;
      }
   }

   int findSet(int i) {
      if(set[i] == i)
         return i;

      return (set[i] = findSet(set[i]));
   }

   void union(int x, int y) {
      x = findSet(x);
      y = findSet(y);

      if( rank[x] > rank[y] )
         set[y] = x;
      else if( rank[x] == rank[y] ){
         set[y] = x;
         rank[x]++;
      }
      else
         set[x] = y;
   }

   boolean isSameSet(int x, int y){
      return ( findSet(x) == findSet(y) ) ;
   }
}

class Maze {

   public static void main(String args[]){
      try{
            int r, c;
            BufferedReader  stdin = new BufferedReader (new InputStreamReader(System.in));
            String temp[] = stdin.readLine().split(" ");
            r = Integer.parseInt(temp[0]);
            c = Integer.parseInt(temp[1]);

            DisjointSet decimal = new DisjointSet( r * c );
            DisjointSet binary = new DisjointSet( r * c );

            int[][] inputMatrix = new int[r][];

            for(int i=0; i<r; i++){

               String s = stdin.readLine();
               inputMatrix[i] = new int[c];

               for(int j=0; j<c; j++){
                  inputMatrix[i][j] = (int)(s.charAt(j) - '0');
               }
            }

            for(int i=0; i<r; i++){
               for(int j=0; j<c; j++){

                  if(i>0){
                     if(inputMatrix[i-1][j] == 0 && inputMatrix[i][j] == 0)
                        binary.union( i*c + j ,(i-1)*c + j);
                     else if(inputMatrix[i-1][j] == 1 && inputMatrix[i][j] == 1)
                        decimal.union( i*c + j ,(i-1)*c + j);

                  }
                  if(j<c-1){
                      if(inputMatrix[i][j+1] == 0 && inputMatrix[i][j] == 0)
                        binary.union( i*c + j ,(i)*c + j + 1);
                     else if(inputMatrix[i][j+1] == 1 && inputMatrix[i][j] == 1)
                        decimal.union( i*c + j ,(i)*c + j + 1);

                  }
                  if(i<r-1){
                      if(inputMatrix[i+1][j] == 0 && inputMatrix[i][j] == 0)
                        binary.union( i*c + j ,(i+1)*c + j);
                     else if(inputMatrix[i+1][j] == 1 && inputMatrix[i][j] == 1)
                        decimal.union( i*c + j ,(i+1)*c + j);

                  }
                  if(j>0){
                      if(inputMatrix[i][j-1] == 0 && inputMatrix[i][j] == 0)
                        binary.union( i*c + j ,(i)*c + j - 1);
                     else if(inputMatrix[i][j-1] == 1 && inputMatrix[i][j] == 1)
                        decimal.union( i*c + j ,(i)*c + j - 1);

                  }

               }
            }

            int n = Integer.parseInt(stdin.readLine());
            for(int i=0; i<n; i++){
               temp = stdin.readLine().split(" ");

               int x1 = Integer.parseInt(temp[0]); x1--;
               int y1 = Integer.parseInt(temp[1]); y1--;
               int x2 = Integer.parseInt(temp[2]); x2--;
               int y2 = Integer.parseInt(temp[3]); y2--;

               if(binary.isSameSet(x1*c + y1, x2*c + y2) && inputMatrix[x1][y1] == 0)
                  System.out.println("binary");
               else if(decimal.isSameSet(x1*c + y1, x2*c + y2) && inputMatrix[x1][y1] == 1)
                  System.out.println("decimal"); 
               else
                  System.out.println("neither");
            }

      }
      catch(Exception e){
         e.printStackTrace();
      }
   }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.