Poj Solution 1753

http://poj.org/problem?id=1753

import java.io.BufferedInputStream;   
import java.util.LinkedList;   
import java.util.Scanner;   
  
 
public class Main {   
    static boolean[] isVisited = new boolean[65536]; 
  
    public static void main(String[] args) {   
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int[][] chessBoard = new int[4][4];   
            for (int i = 0; i < 4; i++) {   
                String ss = scan.nextLine().trim();   
                char[] cs = ss.toCharArray();   
                for (int j = 0; j < 4; j++) {   
                    if (cs[j] == 'b') {   
                        chessBoard[i][j] = 1;//black 1   
                    } else if (cs[j] == 'w') {   
                        chessBoard[i][j] = 0;//white 0   
                    }   
                }   
            }   
            int result = bfs(chessBoard);   
            if (result == -1) {   
                System.out.println("Impossible");   
            } else {   
                System.out.println(result);   
            }   
        }   
    }   
    static int bfs(int[][] chessBoard) {   
        LinkedList<Node> queue = new LinkedList();   
        int id = chessBoardToId(chessBoard);   
        Node node = new Node(id,0);
        if (isWhite(id) || isBlack(id)) {   
            return 0;   
        }   
        isVisited[id] = true;   
        queue.addLast(node);   
        while (!queue.isEmpty()) {   
            node = queue.removeFirst();   
            for (int i = 0; i < 16; i++) {   
                //16 childNode   
                Node nextNode = nextNode(node, i);   
                nextNode.addDepth(); 
                int idid = nextNode.getChessBoardId();   
                if (!isVisited[idid]) {
                    isVisited[idid] = true;   
                    queue.addLast(nextNode);   
                }   
                if (isWhite(idid) || isBlack(idid)) {   
                    int d = nextNode.getDepth();   
                    return d;   
                }   
            }   
        }   
        return -1;   
    }   
  
    static int chessBoardToId(int[][] chessBoard) {   
        int id = 0;   
        for (int i = 0; i < chessBoard.length; i++) {   
            for (int j = 0; j < chessBoard[i].length; j++) {   
                if (chessBoard[i][j] == 1) {   
                    id++;   
                }   
                id <<= 1;
            }   
        }   
        id >>= 1;
        return id;   
    }   
  
    static Node nextNode(Node node, int i) {   
        int id = node.getChessBoardId();   
        int depth = node.getDepth();   
        id ^= (1 << (15 - i));
        if (i >= 4) {   
            id ^= (1 << (15 - i + 4));   
        }   
        if (i <= 11) {
            id ^= (1 << (15 - i - 4));   
        }   
        if (i % 4 > 0) {
            id ^= (1 << (15 - i + 1));   
        }   
        if ((i + 1) % 4 > 0) {
            id ^= (1 << (15 - i - 1));   
        }   
        node = new Node(id,depth);   
        return node;   
    }   
  
    static boolean isWhite(int chessBoardId) {   
        if (chessBoardId == 0) {   
            return true;   
        }   
        return false;   
    }   
  
    static boolean isBlack(int chessBoardId) {   
        if (chessBoardId == 0xFFFF) {
            return true;   
        }   
        return false;   
    }   
}   
  
class Node {   
  
    private int chessBoardId;   
    private int depth;   
  
    public Node(int chessBoardId,int depth) {   
        this.chessBoardId = chessBoardId;   
        this.depth = depth;   
    }   
  
    public int getChessBoardId() {   
        return chessBoardId;   
    }   
  
    public void setChessBoardId(int chessBoardId) {   
        this.chessBoardId = chessBoardId;   
    }   
  
    public int getDepth() {   
        return depth;   
    }   
  
    public void addDepth() {   
        this.depth++;   
    }   
}  


											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *