import java.util.ArrayList;
import java.util.List;

/**
 * 原题 https://leetcode.com/problems/shortest-path-to-get-all-keys/
 * 1. 广度优先搜索
 * 2. 深度优先搜索 timeout
 */
public class _864 {
    static class Solution1 {
        public int shortestPathAllKeys(String[] grid) {
            //(i,j,state) 三元组
            List<int[]> cur = new ArrayList<>();
            int endState = 0;
            int step = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length(); j++) {
                    char ch = grid[i].charAt(j);
                    if (ch >= 'a' && ch <= 'f') {
                        endState |= (1 << ch - 'a');
                    }
                    if (ch == '@') {
                        cur.add(new int[]{i, j, 0});
                    }
                }
            }
            boolean[][][] v = new boolean[grid.length][grid[0].length()][endState];
            for (int[] node : cur) {
                v[node[0]][node[1]][0] = true;
            }
            int[][] dirs = {
                    {0, 1},
                    {0, -1},
                    {-1, 0},
                    {1, 0},
            };
            while (cur.size() > 0) {
                List<int[]> next = new ArrayList<>();
                for (int[] node : cur) {
                    int i = node[0];
                    int j = node[1];
                    int state = node[2];
                    char ch = grid[i].charAt(j);
                    if (ch >= 'a' && ch <= 'f') {
                        state |= 1 << ch - 'a';
                        if (state == endState) {
                            return step;
                        }
                    }
                    for (int[] dir : dirs) {
                        int newI = i + dir[0];
                        int newJ = j + dir[1];
                        if (newI < 0 || newJ < 0 || newI >= grid.length || newJ >= grid[0].length()) {
                            continue;
                        }
                        char newCh = grid[newI].charAt(newJ);
                        if (newCh == '#' || v[newI][newJ][state]) continue;
                        if (newCh >= 'A' && newCh <= 'F') {
                            if ((state & (1 << newCh - 'A')) == 0) continue;
                        }
                        v[newI][newJ][state] = true;
                        next.add(new int[]{newI, newJ, state});
                    }
                }
                cur = next;
                step++;
            }
            return -1;

        }
    }

    static class Solution2 {
        //深度优先搜索行不通，决策的分支太多，导致超时。尝试使用动态规划记录分支，但是没法定义状态
        public int shortestPathAllKeys(String[] grid) {
            //最难的在于，走重复的路
            // 根据key的状态走重复的路
            // i,j,state
            // 最多 64种状态.
            int endState = 0;
            List<int[]> start = new ArrayList<>();
            boolean[] keys = new boolean[6];
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length(); j++) {
                    char ch = grid[i].charAt(j);
                    if (ch >= 'a' && ch <= 'f') {
                        keys[ch - 'a'] = true;
                    }
                    if (ch == '@') {
                        start.add(new int[]{i, j});
                    }
                }
            }
            for (int i = 0; i < keys.length; i++) {
                if (keys[i]) endState += (1 << i);
            }
            int min = Integer.MAX_VALUE;
            for (int[] s : start) {
                min = Math.min(min, dfs(0, new boolean[endState][grid.length][grid[0].length()], grid, s[0], s[1], 0, endState));
            }
            return min == Integer.MAX_VALUE ? -1 : min;
        }

        public int dfs(int state, boolean[][][] v, String[] grid, int i, int j, int step, int endState) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length()) return Integer.MAX_VALUE;
            if (v[state][i][j]) return Integer.MAX_VALUE;
            char cur = grid[i].charAt(j);
            if (cur == '#') return Integer.MAX_VALUE;
            if (cur >= 'A' && cur <= 'F') {
                if ((state & (1 << cur - 'A')) == 0) return Integer.MAX_VALUE;
            }
            int newState = state;// 这里一定要小心，必须要用新的变量接收，否则回溯时，状态不一样
            if (cur >= 'a' && cur <= 'f') {
                newState |= (1 << cur - 'a');
                if (newState == endState) {
                    return step;
                }
            }
            v[state][i][j] = true;
            v[newState][i][j] = true;
            int[][] dirs = {
                    {-1, 0},
                    {1, 0},
                    {0, -1},
                    {0, 1}
            };
            int min = Integer.MAX_VALUE;
            for (int[] dir : dirs) {
                min = Math.min(min, dfs(newState, v, grid, i + dir[0], j + dir[1], step + 1, endState));
            }
            v[state][i][j] = false;
            v[newState][i][j] = false;
            return min;
        }
    }
}