T.java

package ds;


import java.util.*;

public class Test {

    LinkedList<Pos> path = new LinkedList<Pos>();
    boolean[][] used;
    String target;
    boolean found = false;

    char[][] b;

    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0 )
            return false;

        this.b = board;
        used = new boolean[board.length][board[0].length];
        this.target = word;

        backtrack();
        return found;
    }

    private void backtrack() {
//        System.out.println(path);
        if (isComplete()) {
            found = true;
            return;
        }

        List<Pos> nextOptions = nextPositions();
        for (Pos p : nextOptions) {
            path.push(p);
            used[p.i][p.j] = true;

            if (isPartial()) {
                backtrack();
            }

            if (found)
                return;

            used[p.i][p.j] = false;
            path.pop();
        }
    }

    private boolean isComplete(){
        return target.length() == path.size();
    }

    public boolean isPartial() {
        Pos p = path.peek();
        return target.charAt(path.size() - 1) == b[p.i][p.j];
    }

    boolean isLegal(Pos p){
        if(p.i<0 || p.i>= b.length || p.j <0 || p.j >= b[0].length || used[p.i][p.j])
            return false;
        return true;
    }

    List<Pos> nextPositions(){
        List<Pos> poses = new LinkedList<Pos>();
        // first
        if(path.isEmpty()){
            for(int i=0;i<b.length;i++){
                for(int j=0;j<b[0].length;j++){
                    poses.add(new Pos(i,j));
                }
            }
            return poses;
        }

        Pos p = path.peek();
        Pos t = p.down();
        if(isLegal(t)) poses.add(t);
        t = p.top();
        if(isLegal(t)) poses.add(t);
        t = p.right();
        if(isLegal(t)) poses.add(t);
        t = p.left();
        if(isLegal(t)) poses.add(t);

        return poses;
    }


    static class Pos{
        int i;

        int j;
        Pos(int i,int j){this.i=i;this.j=j;}
        Pos left(){return new Pos(i,j-1);}
        Pos right(){return new Pos(i,j+1);}
        Pos top(){return new Pos(i-1,j);}
        Pos down(){return new Pos(i+1,j);}

        public String toString(){return i + "_" + j;}
    }


    public static void main(String[] args){
        char[][] b = new char[][]{
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".toCharArray(),
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".toCharArray(),
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".toCharArray(),
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab".toCharArray()
        };
        System.out.println(new Test().exist(b,"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"));
    }
}