Solving Graph Problems (Part 2) - BFS

Problem Source: UVA Online Judge - 10067

Brief Analysis: It could be easily identified this is a BFS problem. Only one optimization here is to build graph first time before running any test case. Building graph for each test case could get TLE verdict.

Java Code:

public class Main {

    static final int WHITE = 0;
    static final int GRAY = 1;
    static final int BLACK = 2;

    static final int MAX_NUMBER = 10000;

    static List<Integer>[] G;
    static int[] color;
    static int[] dist;
    static Queue<Integer> Q;
    static int source, dest;

    static int forbidCount;
    static int[] forbids;

    static void BFS(int s) {
        int u, v;
        color = new int[MAX_NUMBER];
        dist = new int[MAX_NUMBER];
        for (int i = 0; i < MAX_NUMBER; i++) dist[i] = Integer.MAX_VALUE;
        Q = new LinkedList<>();

        color[s] = GRAY;
        dist[s] = 0;
        Q.add(s);

        while (!Q.isEmpty()) {
            u = Q.poll();

            if (u == dest) break;

            for (int i = 0; i < G[u].size(); i++) {
                v = G[u].get(i);
                if (color[v] == WHITE && forbids[v] != -1) {
                    color[v] = GRAY;
                    dist[v] = dist[u] + 1;
                    Q.add(v);
                }
            }
            color[u] = BLACK;
        }
    }

    static void preBuildGraph() {
        int d1, d2, d3, d4;
        int u, v;

        G = new ArrayList[MAX_NUMBER];
        for (int i = 0; i < MAX_NUMBER; i++) G[i] = new ArrayList<>();

        // Try all possible wheel rotations
        for (int config = 0; config < MAX_NUMBER; config++) {
            d1 = (config / 1000) % 10;
            d2 = (config / 100) % 10;
            d3 = (config / 10) % 10;
            d4 = (config / 1) % 10;

            // 1st wheel left
            v = (d1 - 1 < 0) ? makeNumber(9, d2, d3, d4) : makeNumber(d1-1, d2, d3, d4);
            G[config].add(v);

            // 1st wheel right
            v = (d1 + 1 > 9) ? makeNumber(0, d2, d3, d4) : makeNumber(d1+1, d2, d3, d4);
            G[config].add(v);

            // 2nd wheel left
            v = (d2 - 1 < 0) ? makeNumber(d1, 9, d3, d4) : makeNumber(d1, d2-1, d3, d4);
            G[config].add(v);

            // 2nd wheel right
            v = (d2 + 1 > 9) ? makeNumber(d1, 0, d3, d4) : makeNumber(d1, d2+1, d3, d4);
            G[config].add(v);

            // 3rd wheel left
            v = (d3 - 1 < 0) ? makeNumber(d1, d2, 9, d4) : makeNumber(d1, d2, d3-1, d4);
            G[config].add(v);

            // 3rd wheel right
            v = (d3 + 1 > 9) ? makeNumber(d1, d2, 0, d4) : makeNumber(d1, d2, d3+1, d4);
            G[config].add(v);

            // 4th wheel left
            v = (d4 - 1 < 0) ? makeNumber(d1, d2, d3, 9) : makeNumber(d1, d2, d3, d4-1);
            G[config].add(v);

            // 4th wheel right
            v = (d4 + 1 > 9) ? makeNumber(d1, d2, d3, 0) : makeNumber(d1, d2, d3, d4+1);
            G[config].add(v);
        }
    }

    static int makeNumber(int d1, int d2, int d3, int d4) {
        return ((d1 * 10 + d2) * 10 + d3) * 10 + d4;
    }

    public static void main(String[] args) {
        Scanner scanner = inputFromFile();

        preBuildGraph();

        int TC, tc;

        TC = scanner.nextInt();

        for (tc = 1; tc <= TC; tc++) {
            source = dest = 0;
            for (int i = 0; i < 4; i++) source = source * 10 + scanner.nextInt();
            for (int i = 0; i < 4; i++) dest = dest * 10 + scanner.nextInt();

            forbidCount = scanner.nextInt();
            forbids = new int[MAX_NUMBER];
            for (int i = 0; i < forbidCount; i++) {
                int temp = 0;
                for (int j = 0; j < 4; j++) temp = temp * 10 + scanner.nextInt();
                forbids[temp] = -1;
            }

            if (forbids[source] == -1 || forbids[dest] == -1) {
                System.out.println("-1");
                continue;
            }

            BFS(source);

            if (dist[dest] == Integer.MAX_VALUE) System.out.println("-1");
            else System.out.println(dist[dest]);
        }
    }

    static Scanner inputFromFile() {
        try { return new Scanner(new FileInputStream("input.txt")); }
        catch (FileNotFoundException e) { e.printStackTrace(); }
        return null;
    }

    static Scanner inputFromSystem() {
        return new Scanner(System.in);
    }
}

Few others BFS problems:

  1. UVA Online Judge - 10150
  2. UVA Online Judge - 11624
  3. UVA Online Judge - 11792 (Hard)
  4. UVA Online Judge - 11049
  5. UVA Online Judge - 11352
Blog Comments powered by Disqus.

Next Post Previous Post