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.
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;
}
}
