[Solved] Um, Hi I’m a Beginner and don’t know how to speed my code up. My homework is to write a program for CCC ’20 S2 – Escape Room faster than two seconds

by


Take a look at this. I have tried grids 10×10 – solved in cca 3-4ms (including input), which is far below 2s.

class Escape_Room {

    static boolean method(Map<Integer, Set<Integer>> transitionMap, int size, int start) {
        Set<Integer> closed = new HashSet<Integer>(size);
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        int key;
        while(!q.isEmpty()) {
            key = q.poll();
            if(closed.contains(key)) {
                continue;
            }
            if(key == size) {
                return true;
            }
            closed.add(key);
            if(transitionMap.containsKey(key)) {
                for (int i : transitionMap.get(key)) {
                    if(i == size) {
                        return true;
                    }
                    if (!closed.contains(i)) {
                        q.add(i);
                    }
                }
            }
        }
        return false;
    }

}

public class Solution {
    static StringBuilder str;
    static InputStreamReader in;
    static int buf;

    private static int readInt() throws IOException {
        buf = 0;
        int c;
        do {
            c = in.read(); 
        } while (c < '0' || c > '9' );
        do {
            buf = 10*buf + c - 48;
            c = in.read();
        } while (!(c < '0' || c > '9' ));
        return buf;
    }

    public static void main(String[] args) throws IOException {
        long t1 = System.currentTimeMillis();
        Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
        in = new InputStreamReader(new BufferedInputStream(System.in));
        int m=readInt();
        int n=readInt();
        int size = m*n;
        Map<Integer, Set<Integer>> transitionMap = new HashMap<>(size);
        Set<Integer> temp;
        int start = 0, key = 0;

        for (int i = 0, j, value; i < m; i++) {
            for(j = 0; j < n; ++j) {
                key = (i+1)*(j+1);
                value = readInt();
                if(i == 0 && j == 0) {
                    start = key;
                }
                if (transitionMap.containsKey(key)) {
                    transitionMap.get(key).add(value);
                } else {
                    temp = new HashSet<>(size);
                    temp.add(value);
                    transitionMap.put(key, temp);
                }
            }
        }
        long t2 = System.currentTimeMillis();       
        boolean o = Escape_Room.method(transitionMap, size, start);
        long t3 = System.currentTimeMillis();
        System.out.println(o?"yes":"no");
        System.out.println("Finished in: " + (t3 - t1) + "ms. Input: " + (t2 - t1)  + "ms. Solving: " + (t3 - t2) + " ms.");
    }
}

solved Um, Hi I’m a Beginner and don’t know how to speed my code up. My homework is to write a program for CCC ’20 S2 – Escape Room faster than two seconds