The problem statement is : https://www.spoj.com/problems/ADV04F1/
I coded the following brute-force BFS in java, and it’s giving TLE. I found a similar approach coded in C++ at : https://github.com/mukel/ProgrammingContests/blob/master/OldStuff/SPOJ/new15/adv04f1.cpp
and that got accepted. Since there is no restriction on the language in the problem statement. Any help that could help me optimize my code and get it accepted, will be appreciated.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String args[]) throws IOException{
InputReader ip = new InputReader(System.in);
OutputWriter op = new OutputWriter(System.out);
Solution sol = new Solution();
int t = ip.readInt();
while(t-- > 0){
op.println(sol.bfs(ip.readInt(), ip.readInt(), ip.readInt(), ip.readInt()));
}
op.close();
}
}
class Solution {
int N = 70;
Queue<Node> queue;
char[][][][] visited ;
int bfs(int a, int b, int c, int d){
visited = new char[71][71][71][71];
Node start = new Node(1, 2, 3, 4, 48);
Node target = new Node(a, b, c, d, 48);
if(start.equals(target))
return 0;
queue = new LinkedList<Node>();
queue.add(start);
visited[1][2][3][4] = '1';
while(!queue.isEmpty()){
Node curr = queue.poll();
for(Node next : nextConfigs(curr)){
if(next.equals(target))
return next.dist - '0';
int hc = next.hashCode();
if(visited[next.a][next.b][next.c][next.d] != '1'){
visited[next.a][next.b][next.c][next.d] = '1';
queue.offer(next);
}
}
}
return 0;
}
ArrayList<Node> nextConfigs(Node currConfig){
int a = currConfig.a;
int b = currConfig.b;
int c = currConfig.c;
int d = currConfig.d;
int currDist = currConfig.dist;
ArrayList<Node> res = new ArrayList<Node>(30);
// for d
if(d + 1 < N)
res.add(new Node(a, b, c, d + 1, currConfig.dist+1));
// for c
if(c + 1 != d)
res.add(new Node(a, b, c + 1, d, currConfig.dist+1));
if(b + 1 != c)
res.add(new Node(a, b + 1, c, d, currConfig.dist+1));
if(a + 1 != b)
res.add(new Node(a + 1, b, c, d, currConfig.dist+1));
if(d - 1 != c)
res.add(new Node(a, b, c, d-1, currDist+1));
if(c - 1 != b)
res.add(new Node(a, b, c-1, d, currDist+1));
if(b - 1 != a)
res.add(new Node(a, b-1, c, d, currDist+1));
if(a - 1 > 0)
res.add(new Node(a-1, b, c, d, currDist+1));
if((d<<1) - c < N)
res.add(new Node(a, b, d, (d<<1) - c, currDist+1));
// for b
int temp = (c<<1) - b;
if(temp < N){
if(temp < d)
res.add(new Node(a, c, temp, d, currDist+1));
if(temp > d)
res.add(new Node(a, c, d, temp, currDist+1));
}
temp = (d<<1) - b;
if(temp < N)
res.add(new Node(a, c, d, temp, currDist+1));
// for a
temp = (b<<1) - a;
if(temp < N){
if(temp < c)
res.add(new Node(b, temp, c, d, currDist+1));
if(temp > c && temp < d)
res.add(new Node(b, c, temp, d, currDist+1));
if(temp > d)
res.add(new Node(b, c, d, temp, currDist+1));
}
temp = (c<<1) - a;
if(temp < N){
if(temp < d)
res.add(new Node(b, c, temp, d, currDist+1));
if(temp > d)
res.add(new Node(b, c, d, temp, currDist+1));
}
if((d<<1) - a < N)
res.add(new Node(b, c, d, (d<<1) -a, currDist+1));
// -------------------------------------------------------------
// for a
// for b
if((a<<1) - b > 0)
res.add(new Node((a<<1) - b, a, c, d, currDist+1));
// for c
temp = (b<<1) - c;
if(temp > 0){
if(temp > a)
res.add(new Node(a, temp, b, d, currDist+1));
if(temp < a)
res.add(new Node(temp, a, b, d, currDist+1));
}
temp = (a<<1) - c;
if(temp > 0)
res.add(new Node(temp, a, b, d, currDist+1));
// for d
temp = (c<<1) - d;
if(temp > 0){
if(temp > b)
res.add(new Node(a ,b, temp, c, currDist+1));
if(temp > a && temp < b)
res.add(new Node(a, temp, b, c, currDist+1));
if(temp < a)
res.add(new Node(temp, a, b, c, currDist+1));
}
temp = (b<<1) - d;
if(temp > 0){
if(temp < a)
res.add(new Node(temp,a, b, c, currDist+1));
if(temp > a)
res.add(new Node(a, temp, b, c, currDist+1));
}
if((a<<1) - d > 0)
res.add(new Node((a<<1) - d, a, b, c, currDist+1));
return res;
}
}
class Node {
int a;
int b;
int c;
int d;
int dist;
Node(int a, int b, int c,int d, int dst){
this.a = a;
this.b = b;
this.c = c;
this.d = d;
this.dist = dst;
}
// boolean equals(Node other){
// if(this.a == other.a && this.b == other.b && this.c == other.c && this.d == other.d)
// return true;
// return false;
// }
public String toString(){
return a + ", " + b + ", " + c + ", " + d + " (" + dist + ") \n";
}
// public int hashCode(){
// }
@Override
public int hashCode() {
return a*2 + b*3 + c*5 + d*7;
}
@Override
public boolean equals(final Object obj) {
Node other = (Node) obj;
if(this.a == other.a && this.b == other.b && this.c == other.c && this.d == other.d)
return true;
return false;
}
}
// fast I/O
class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public static boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public char readCharacter() {
int c = read();
while (isSpaceChar(c))
c = read();
return (char) c;
}
}
class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(outputStream);
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object...objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0)
writer.print(' ');
writer.print(objects[i]);
}
}
public void println(Object...objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
}
