apu_improvement_phase.java

import java.util.*;
import java.io.*;
import java.math.*;

/**
 * The machines are gaining ground. Time to show them what we're really made of...
 **/
class Player {

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int width = in.nextInt(); // the number of cells on the X axis
        in.nextLine();
        int height = in.nextInt(); // the number of cells on the Y axis
        in.nextLine();
        
        // Need to build the matrix first
        Board board = new Board(width, height, new Pair[width][height], 0);
        Pair[] latestY = new Pair[width];
        
        for (int y = 0; y < height; y++) {
            String line = in.nextLine();
            System.err.println(line);
            Pair latestX = null;
            for(int x = 0; x < width; x++){
                char c = line.charAt(x);
                if (c != '.'){
                    int links =  Character.getNumericValue(c);
                    Pair current = new Pair(x,y,links);
                    board.pairs[x][y] = current;
                    board.pending += links;
                    if (latestX != null){
                      latestX.right = current;
                      current.left = latestX;
                    } 
                    if (latestY[x] != null) {
                        latestY[x].below = current;
                        current.up = latestY[x];
                    }
                    latestX = current;
                    latestY[x] = current;
                }
            }
        }
        
        backtrack(new LinkedList(), board, 0, 0);
        
    }
    
    static boolean backtrack(Deque<Move> moves, Board b, int x, int y) {
        System.err.println(b);
        if (isASolution(b)) {
            processSolution(moves);
            return true;
        } else {
            // Find next valid node
            Pair p = null;
            while(p == null || p.missingLinks() == 0) {
                if (x == b.width){
                  x = 0;
                  y++;
                } 
                if (y == b.height) y = 0;
                
                p = b.pairs[x][y];
                if (p!= null)  System.err.println("x = " + x + " y = " + y);
                x++;
            }
            List<Move> candidates = constructCandidates(moves, p);

            for(Move move : candidates) {
                makeMove(b, move);
                moves.add(move);
                System.err.println("Make move: " + move);
                boolean finished = backtrack(moves, b, x, y);
                if (finished) return true;
                
                unmakeMove(b, move);
                moves.removeLast();
                System.err.println("Unmake move: " + move);
            }
        }
        return false;
    }
    
    // Check if there are no pending links
    static boolean isASolution(Board b){
        return b.pending == 0;
    }
    
    static void processSolution(Deque<Move> moves) {
        // Print all moves
        for(Move m : moves) {
            System.out.println(m.origin + " " + m.destination + " 1");
        }
    }
    
    static List<Move> constructCandidates(Deque<Move> moves, Pair c) {
        // Given the current state, build list of moves
        // Should make sure we don't cross links
        List<Move> candidates = new ArrayList<Move>();
        if (c.missingLinks() > 0 && c.right != null  && c.rightLinks < 2  && c.right.missingLinks()>0){
            candidates.add(new Move(c, c.right, 0));
        }
        
        if (c.missingLinks() > 0 && c.below != null && c.belowLinks < 2 && c.below.missingLinks()>0){
            candidates.add(new Move(c, c.below, 1));
        }
        
        if (c.missingLinks() > 0 && c.left != null  && c.leftLinks < 2 && c.left.missingLinks()>0){
            candidates.add(new Move(c, c.left, 2));
        }
        
        if (c.missingLinks() > 0 && c.up != null  && c.upLinks < 2 && c.up.missingLinks()>0){
            candidates.add(new Move(c, c.up, 3));
        }
        return candidates;
    }
    
    static void makeMove(Board b, Move m) {
        b.pending-=2;
        switch(m.direction) {
            case 0 :
                m.origin.rightLinks++;
                m.destination.leftLinks++;
                break;
            case 1:
                m.origin.belowLinks++;
                m.destination.upLinks++;
                break;
            case 2:
                m.origin.leftLinks++;
                m.destination.rightLinks++;
                break;
            case 3:
                m.origin.upLinks++;
                m.destination.belowLinks++;
                break;
            default :
              System.out.println("ERROR!!!!");
        }
    }

    static void unmakeMove(Board b, Move m) {
        b.pending+=2;
        switch(m.direction) {
            case 0 :
                m.origin.rightLinks--;
                m.destination.leftLinks--;
                break;
            case 1:
                m.origin.belowLinks--;
                m.destination.upLinks--;
                break;
            case 2:
                m.origin.leftLinks--;
                m.destination.rightLinks--;
                break;
            case 3:
                m.origin.upLinks--;
                m.destination.belowLinks--;
                break;
            default :
              System.out.println("ERROR!!!!");
        }
    }


    static class Move {
        Pair origin, destination;
        int direction; // 0 - right, 1 - below, 2 - left, 3 - up
        Move(Pair orig, Pair dest, int dir) {
            this.origin = orig;
            this.destination = dest;
            this.direction = dir;
        }
        public String toString() {
            return origin + " " + destination;
        }
    }   
    
    private static class Board {
        Pair[][] pairs;
        int width, height, pending;
        Board(int width, int height, Pair[][] pairs, int pending) {
            this.pairs = pairs;
            this.pending = pending;
            this.width = width;
            this.height = height;
        }
        public String toString() {
            return "Board: " + this.pending;
        }
    }
    
    private static class Pair {
        Pair right = null;
        Pair below = null;
        Pair left = null;
        Pair up = null;
        final int amount;
        
        int rightLinks = 0;
        int leftLinks = 0;
        int belowLinks = 0;
        int upLinks = 0;
        
        String me;
        int x, y;

        Pair(int x, int y, int amount){
            this.me = x + " " + y;
            this.x = x;
            this.y = y;
            this.amount = amount;
        }
        
        int missingLinks() {
            int missing =  amount - (rightLinks + leftLinks + belowLinks + upLinks);
            return missing;
        }
        
        public String toString() {
            return x + " " + y;
        }
    }
}