Boggle Game

import java.util.*;

class Pair {
    int x;
    int y;
    public Pair(int x, int y){
        this.x = x;
        this.y = y;
    }
}

class TrieNode {
    boolean isWord;
    String word;
    TrieNode[] children;
    public TrieNode (){
        isWord = false;
        children = new TrieNode[26];
        word = "";
    }

    public void insert(String word, int index){
        if (word.length() == index){
            this.word = word;
            this.isWord = true;
            return;
        }
        int pos = word.charAt(index) - 'a';
        if (this.children[pos] == null){
            this.children[pos] = new TrieNode();
        }
        this.children[pos].insert(word, index + 1);
    }

}
public class BoggleGame {
    static int max;
    static HashSet<String> dict;
    static int maxLen;
    static List<String> words = new LinkedList<>();
    static List<String> ans = new LinkedList<>();

    public static void main(String[] args){
//        String[] inputs = {"lintcodeisnice","lintcodeisgood"};
        String [] inputs = {"lintcodeisnice","lintcodeisgood","uilwowwwwowwqw","poiuywqaazxcvw","poiuytrewzxcvb","tyuwqazxhuwqaz"};
        char[][] board = new char[6][14];
//        String[] inputs = {"abc","def","ghi"};
        for (int i = 0; i < inputs.length; i++){
            board[i] = inputs[i].toCharArray();
            System.out.println(Arrays.toString(board[i]));
        }
        String[] words = {"a","lint","code","ccode","poiy","ppty","cvbwwd","ngoo"};
        int result = boggleGame(board, words);

        System.out.println(result);
    }

    //1. 没有Trie的version
    public static int boggleGame(char[][] board, String[] words){
        if (board.length == 0 || board[0].length== 0 || words.length == 0){
            return 0;
        }

        int m = board.length;
        int n = board[0].length;
        for (String word: words){
            maxLen = Math.max(maxLen, word.length());
        }
//        dict = new HashSet<String>(Arrays.asList(words));
        TrieNode root = new TrieNode();
        for (String word : words){
            root.insert(word, 0);
        }
        int[][] vis = new int[m][n];
        dfs(board, vis, 0, 0, root);
        System.out.println(Arrays.toString(ans.toArray()));
        return ans.size();

    }

    private static void dfs(char[][] board, int[][] vis, int x, int y, TrieNode root){
        for (int i = x; i < board.length; i++){
            for (int j = y; j < board[0].length; j++){
                //get all paths from i, j position
                List<List<Pair>> paths = new ArrayList<>();
                List<Pair> currentPath = new ArrayList<>();
                getPaths(board, vis, i, j, paths, currentPath, root);
                System.out.println(root.word);
                for (List<Pair> path : paths){
                    StringBuilder sb = new StringBuilder();
                    for (Pair p : path){
                        sb.append(board[p.x][p.y]);
                        vis[p.x][p.y] = 1;
                    }
                    words.add(sb.toString());
                    System.out.println("Currently in words: ");
                    System.out.println("Words size " + words.size());
                    for (int t = 0; t < words.size(); t++){
                        System.out.println(words.get(t));
                    }
                    if (words.size() > ans.size()){
                        ans.clear();
                        ans.addAll(words);
                    }
                    for (int k = 0; k < vis.length; k++){
                        System.out.println(Arrays.toString(vis[k]));
                    }
                    System.out.println("Next to dfs " + i + " " + j);
                    dfs(board, vis, i, j, root);
                    for (Pair p : path){
                        vis[p.x][p.y] = 0;
                    }
                    words.remove(words.size() - 1);
                }
            }
            y = 0;
        }
    }

    private  static void getPaths(char[][] board, int[][] vis, int i, int j, List<List<Pair>> paths
    , List<Pair> currentPath, TrieNode root){

        if (i >= board.length || i < 0 || j >= board[0].length || j < 0
                || vis[i][j] == 1 || root.children[board[i][j] - 'a'] == null){
            return;
        }


        StringBuilder sb = new StringBuilder();
        // get the current TrieNode
        root = root.children[board[i][j] - 'a'];

        //check if it's a word
        if (root.isWord){
            List<Pair> clone = new ArrayList<>(currentPath);
            clone.add(new Pair(i, j));
            paths.add(clone);
            return;
        }

        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, -1, 0, 1};

        //mark current position as visited
        vis[i][j] = 1;
        currentPath.add(new Pair(i, j));
        for (int t = 0; t < 4; t++){

            int x = i + dx[t];
            int y = j + dy[t];

            getPaths(board, vis, x, y, paths, currentPath, root);
        }
        currentPath.remove(currentPath.size() - 1);
        vis[i][j] = 0;
    }