从游戏中学算法——鸣潮溢彩画解答算法探索

import java.util.List;

/**
 * 溢彩画解题器接口
 */
public interface ColorPaintingSolver {
    /**
     * 解决溢彩画问题
     *
     * @param grid        颜色矩阵
     * @param maxStep     最大步数
     * @param targetColor 目标颜色
     * @return 解题步骤，找不到方案则返回null
     */
    List<Step> solve(Color[][] grid, int maxStep, Color targetColor);

    /**
     * 对于支持记录尝试次数的解题器，返回尝试次数
     *
     * @return 尝试次数
     */
    default long getTryCount() {
        return -1;
    }
}

/**
 * 颜色枚举
 */
public enum Color {
    BLUE('b', "\u001B[104;30m"),
    RED('r', "\u001B[101;30m"),
    YELLOW('y', "\u001B[103;30m"),
    GREEN('g', "\u001B[102;30m"),
    BLOCK('x', "\u001B[8m"),
    ;
    /**
     * 题目中代表该颜色的字符
     */
    public final char c;
    /**
     * 用于打印题目用的颜色码
     */
    public final String asciiColor;

    Color(char c, String asciiColor) {
        this.c = c;
        this.asciiColor = asciiColor;
    }

    public static Color of(char c) {
        for (Color color : values()) {
            if (color.c == c) {
                return color;
            }
        }
        throw new IllegalArgumentException("unknown color: " + c);
    }

    public String toString(int id) {
        if (this == BLOCK) {
            return asciiColor + "   " + "\u001B[0m";
        }
        return asciiColor + String.format("%2d ", id) + "\u001B[0m";
    }

    public String toString() {
        return asciiColor + name() + "\u001B[0m";
    }
}

/**
 * 坐标
 */
public record Point(int row, int col) {
    @Override
    public String toString() {
        return "(" + row + ", " + col + ")";
    }
}

/**
 * 一次步骤，包含点击坐标和颜色
 */
public record Step(Point click, Color color) {
    @Override
    public String toString() {
        return "click " + click + " with " + color;
    }
}

import java.util.*;

/**
 * A*算法解题器
 */
public class AStarSolver implements ColorPaintingSolver {
    /**
     * A*算法的状态
     */
    private record State(List<Step> steps, Map<Integer, Region> regions, UnionFind mergedFind, int gWeight) implements Comparable<State> {
        public State(State state) {
            List<Step> steps = new ArrayList<>(state.steps.size() + 1);
            steps.addAll(state.steps);
            this(new ArrayList<>(steps), SolverUtil.copyRegions(state.regions), new UnionFind(state.mergedFind), state.gWeight);
        }

        private int g() {
            return steps.size() * gWeight; // 平衡与h的权重
        }

        private int h() {
            return regions.size(); // 剩余分区数
        }

        /**
         * 点击分区，改变颜色
         */
        public void click(int regionId, Color color) {
            // 点击分区，改变颜色
            regions.get(regionId).color = color;
            // 添加点击步骤
            steps.add(new Step(regions.get(regionId).clickPos, color));
            // 合并分区
            SolverUtil.mergeRegions(regions, regionId, mergedFind);
        }

        @Override
        public int compareTo(State o) {
            // 计算当前状态的启发式函数值用于优先级排序
            return Integer.compare(this.g() + this.h(), o.g() + o.h());
        }

        /**
         * 判断当前状态是否相同
         * 只要所有分区的颜色相同就认为是相同的状态
         * 用于记录访问过的状态
         */
        @Override
        public boolean equals(Object o) {
            State state = (State) o;

            // 从mergedFind中获取分区的当前被哪个分区合并了，进而获取到分区当前的颜色
            int initialSize = mergedFind.initialSize();
            for (int i = 0; i < initialSize; i++) {
                Color color = regions.get(mergedFind.find(i)).color;
                Color otherColor = state.regions.get(state.mergedFind.find(i)).color;
                if (color != otherColor) {
                    return false;
                }
            }
            return true;
        }

        @Override
        public int hashCode() {
            int hash = 7;
            for (int i = 0; i < mergedFind.initialSize(); i++) {
                hash = 31 * hash + regions.get(mergedFind.find(i)).color.ordinal() + 1;
            }
            return hash;
        }
    }

    /**
     * 并查集，用于记录分区被哪个分区合并了
     * 以便于在A*状态的equals方法中判断状态是否相同
     */
    public static class UnionFind {
        private final int[] root;

        public UnionFind(int n) {
            root = new int[n];
            for (int i = 0; i < n; i++) {
                root[i] = i;
            }
        }

        /**
         * 从另一个并查集复制
         */
        public UnionFind(UnionFind other) {
            this.root = new int[other.root.length];
            System.arraycopy(other.root, 0, this.root, 0, other.root.length);
        }

        public int find(int x) {
            return root[x] == x ? x : (root[x] = find(root[x])); // 路径压缩
        }

        public void union(int parent, int son) {
            int rootParent = find(parent);
            int rootSon = find(son);
            if (rootParent != rootSon) {
                root[rootSon] = rootParent; // 合并
            }
        }

        public int initialSize() {
            return root.length;
        }
    }

    // 用于统计尝试次数
    int tryCount = 0;

    @Override
    public long getTryCount() {
        return tryCount;
    }

    @Override
    public List<Step> solve(Color[][] grid, int maxStep, Color targetColor) {
        // 预处理，将颜色矩阵解析为分区
        Map<Integer, Region> regions = SolverUtil.findRegionsFromGrid(grid);

        // 计算g函数的权重
        int gWeight = Math.max(1, regions.size() / maxStep / 2);

        // 初始化优先队列
        PriorityQueue<State> pq = new PriorityQueue<>();
        State initialState = new State(new ArrayList<>(), regions, new UnionFind(regions.size()), gWeight);
        pq.add(initialState);

        // 记录访问过的状态
        Map<State, Integer> visited = new HashMap<>();

        while (!pq.isEmpty()) {
            State currentState = pq.poll();

            // 判断是否全是目标色
            var colorCount = SolverUtil.getColorCount(currentState.regions, targetColor);
            if (colorCount.count() == 1 && colorCount.hasTargetColor()) {
                return currentState.steps;
            }
            // 步数充足，且可以加一步全染成目标色，也是一种解法
            if (colorCount.count() == 1 && currentState.steps.size() < maxStep) {
                Point firstClickPos = currentState.regions.values().iterator().next().clickPos;
                currentState.steps.add(new Step(firstClickPos, targetColor));
                return currentState.steps;
            }

            // 判断是否超过最大步数
            if (currentState.steps.size() >= maxStep) {
                continue;
            }

            // 判断颜色数和步骤数，进行剪枝
            if (currentState.steps.size() + (colorCount.count() - (colorCount.hasTargetColor() ? 1 : 0)) > maxStep) {
                continue;
            }

            // 下一轮状态
            for (Region region : currentState.regions.values()) {
                for (Color nextColor : SolverUtil.getNeighborsColor(currentState.regions, region.id)) {
                    // 计算新状态
                    State nextState = new State(currentState);
                    nextState.click(region.id, nextColor);

                    // 判断是否已经访问过步数一致或者更优的状态
                    if (visited.getOrDefault(nextState, Integer.MAX_VALUE) <= nextState.g()) {
                        continue; // 已经访问过，跳过
                    }
                    visited.put(nextState, nextState.g()); // 记录访问过的状态

                    // 添加新状态到优先队列
                    pq.add(nextState);
                    tryCount++;
                }
            }
        }
        return null; // 没有找到解
    }
}

import java.util.*;

/**
 * 表示一个联通分区
 */
public class Region {
    /**
     * 该分区的索引
     */
    public int id;
    /**
     * 该分区的一个可点击坐标
     */
    public Point clickPos;
    /**
     * 该分区的颜色
     */
    public Color color;
    /**
     * 该分区的邻接分区索引列表
     */
    public Set<Integer> neighbors = new HashSet<>();

    public Region(int id, Point clickPos, Color color) {
        this.id = id;
        this.clickPos = clickPos;
        this.color = color;
    }

    public static Region copy(Region region) {
        Region newRegion = new Region(region.id, region.clickPos, region.color);
        newRegion.neighbors = new HashSet<>(region.neighbors);
        return newRegion;
    }
}

import java.util.*;

/**
 * 工具类，和解题算法无关的部分放在这里
 */
public class SolverUtil {
    private static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    /**
     * BFS算法寻找分区
     */
    public static Map<Integer, Region> findRegionsFromGrid(Color[][] grid) {
        Map<Integer, Region> regions = new HashMap<>();
        int n = grid.length, m = grid[0].length;
        int[][] regionIds = new int[n][m];
        for (int[] row : regionIds) Arrays.fill(row, -1);

        int currentId = 0;

        // 组合联通块
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (regionIds[i][j] == -1 && grid[i][j] != Color.BLOCK) {
                    Color color = grid[i][j];
                    Queue<Point> q = new LinkedList<>();
                    q.add(new Point(i, j));
                    regionIds[i][j] = currentId;

                    while (!q.isEmpty()) {
                        Point p = q.poll();
                        for (int[] d : dirs) {
                            int x = p.row() + d[0], y = p.col() + d[1];
                            if (x >= 0 && x < n && y >= 0 && y < m) {
                                if (regionIds[x][y] == -1) {
                                    if (grid[x][y] == color) {
                                        regionIds[x][y] = currentId;
                                        q.add(new Point(x, y));
                                    }
                                }
                            }
                        }
                    }
                    Region region = new Region(currentId, new Point(i, j), color);
                    regions.put(currentId++, region);
                }
            }
        }

        // 建立邻接关系
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (regionIds[i][j] == -1) {
                    continue;
                }
                for (int[] d : dirs) {
                    int x = i + d[0], y = j + d[1];
                    if (x >= 0 && x < n && y >= 0 && y < m) {
                        if (regionIds[x][y] != -1 && regionIds[x][y] != regionIds[i][j]) {
                            regions.get(regionIds[i][j]).neighbors.add(regionIds[x][y]);
                        }
                    }
                }
            }
        }

        return regions;
    }

    /**
     * 深拷贝分区表
     */
    public static Map<Integer, Region> copyRegions(Map<Integer, Region> regions) {
        Map<Integer, Region> copyRegions = new HashMap<>(regions.size() * 2);
        for (Integer key : regions.keySet()) {
            copyRegions.put(key, Region.copy(regions.get(key)));
        }
        return copyRegions;
    }

    /**
     * 计算当前画面颜色数量
     */
    public static ColorCountResult getColorCount(Map<Integer, Region> regions, Color targetColor) {
        int colorCount = 0;
        boolean hasTargetColor = false;
        boolean[] colors = new boolean[4];
        for (Region region : regions.values()) {
            colors[region.color.ordinal()] = true;
        }
        for (int i = 0; i < colors.length; i++) {
            if (colors[i]) {
                colorCount++;
                if (Color.values()[i] == targetColor) {
                    hasTargetColor = true;
                }
            }
        }
        return new ColorCountResult(colorCount, hasTargetColor);
    }

    /**
     * 合并分区
     *
     * @param regions       分区表
     * @param clickRegionId 点击的分区id
     * @param mergedFind    用于记录被合并分区归属分区的并查集
     */
    public static void mergeRegions(Map<Integer, Region> regions, int clickRegionId, AStarSolver.UnionFind mergedFind) {
        Set<Integer> clickNeighbors = regions.get(clickRegionId).neighbors;
        Integer[] clickNeighborsCopy = clickNeighbors.toArray(new Integer[0]);
        for (int neighborId : clickNeighborsCopy) {
            Region neighborRegion = regions.get(neighborId);

            // 如果邻接分区的颜色和当前分区颜色相同，则合并
            if (neighborRegion.color == regions.get(clickRegionId).color) {
                // 删除被合并的分区
                regions.remove(neighborId);

                // 更新当前分区的邻接分区列表
                for (int neighborNeighborId : neighborRegion.neighbors) {
                    if (neighborNeighborId != clickRegionId) {
                        Set<Integer> neighborNeighbors = regions.get(neighborNeighborId).neighbors;
                        // 从被删除的分区的邻接列表中移除被删除的分区
                        neighborNeighbors.remove(neighborId);
                        // 合并后被删除分区的邻接分区加入当前分区的邻接列表
                        neighborNeighbors.add(clickRegionId);
                        // 当前分区的邻接列表加入被删除分区的邻接分区
                        regions.get(clickRegionId).neighbors.add(neighborNeighborId);
                    }
                }
                clickNeighbors.remove(neighborId);
                mergedFind.union(clickRegionId, neighborId);
            }
        }
    }

    /**
     * 获取点击分区的邻接分区颜色
     *
     * @param regions       分区表
     * @param clickRegionId 点击的分区id
     * @return 邻接分区颜色列表
     */
    public static Set<Color> getNeighborsColor(Map<Integer, Region> regions, int clickRegionId) {
        Set<Color> neighborsColor = new HashSet<>(8);
        for (int neighborId : regions.get(clickRegionId).neighbors) {
            neighborsColor.add(regions.get(neighborId).color);
        }
        return neighborsColor;
    }
}