Java版本的基于计算机视觉的跃动小子保卫主公自动通关计划之执行计划生成篇

九转成圣

发布于 2024-11-24 00:39:39

12100

代码可运行

文章被收录于专栏：csdncsdn

运行总次数：0

代码可运行

Java版本的基于计算机视觉的跃动小子保卫主公自动通关计划之执行计划生成篇

微信小程序跃动小子保卫主公自动通关之执行计划,包含了移动1步,2步,3步,4步消除3个元素,4个元素,5个元素,6个元素,7个元素的所有执行计划,共计20036个

思路

逆向思维,由消除形态推演消除前形态,再计算消除前形态到消除形态最小移动步数和详细过程,此计划只需要生成一次即可,这里生成了3,4,5,6,7个元素移动1步,2步,3步,4步的所有计划,共计20036种,完整的执行计划文件见

基本消除形态

7连只有一种形态

0 0 0 0 0 0 
0 0 0 0 0 0 
0 1 1 1 1 1 
0 0 0 1 0 0 
0 0 0 1 0 0 
0 0 0 0 0 0

6连形态也只有一种形态

0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 1 1 1 1 
0 0 0 1 0 0 
0 0 0 1 0 0 
0 0 0 0 0 0

5连形态(3种)

0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 1 1 1 
0 0 0 1 0 0 
0 0 0 1 0 0 
0 0 0 0 0 0 

0 0 0 0 0 0 
0 0 0 0 0 0 
0 1 1 1 1 1 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0

0 0 0 0 0 0 
0 0 0 0 1 0 
0 0 0 1 0 1 
0 0 0 0 1 0 
0 0 0 0 1 0 
0 0 0 0 0 0

4连形态

0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 1 1 1 1 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0

3连形态

0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 1 1 1 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0

变异消除形态:对基本消除形态旋转90°,180°,270°,水平翻转,垂直翻转后可以得到变异的消除形态,基本形态+变异消除形态为完整的消除形态

完整的执行计划

完整执行计划

执行计划展示

移动一步消除7个元素的执行计划如下

0 0 1 0 0 
1 1 0 1 1 
0 0 1 0 0 
0 0 1 0 0 
到的执行计划
0 0 0 0 0 
1 1 1 1 1 
0 0 1 0 0 
0 0 1 0 0 

{
    "count": 7,
    "finalState": [
        [0,0,0,0,0],
        [1,1,1,1,1],
        [0,0,1,0,0],
        [0,0,1,0,0]
    ],
    "sorted": 0,
    "startCol": 0,
    "startRow": 0,
    "steps": [
        {
            "col": 2,
            "notes": "Swap (0,2) with (1,2) - Move: Down",
            "row": 0,
            "type": "Down"
        }
    ],
    "target": [
        [0,0,1,0,0],
        [1,1,0,1,1],
        [0,0,1,0,0],
        [0,0,1,0,0]
    ]
}

0 0 1 0 
0 0 1 0 
1 1 0 1 
0 0 1 0 
0 0 1 0 
到的执行计划
0 0 1 0 
0 0 1 0 
1 1 1 0 
0 0 1 0 
0 0 1 0 

{
    "count": 7,
    "finalState": [
        [0,0,1,0],
        [0,0,1,0],
        [1,1,1,0],
        [0,0,1,0],
        [0,0,1,0]
    ],
    "sorted": 0,
    "startCol": 0,
    "startRow": 0,
    "steps": [
        {
            "col": 2,
            "notes": "Swap (2,2) with (2,3) - Move: Right",
            "row": 2,
            "type": "Right"
        }
    ],
    "target": [
        [0,0,1,0],
        [0,0,1,0],
        [1,1,0,1],
        [0,0,1,0],
        [0,0,1,0]
    ]
}

0 0 1 0 0 
0 0 1 0 0 
1 1 0 1 1 
0 0 1 0 0 
到的执行计划
0 0 1 0 0 
0 0 1 0 0 
1 1 1 1 1 
0 0 0 0 0 

{
    "count": 7,
    "finalState": [
        [0,0,1,0,0],
        [0,0,1,0,0],
        [1,1,1,1,1],
        [0,0,0,0,0]
    ],
    "sorted": 0,
    "startCol": 0,
    "startRow": 0,
    "steps": [
        {
            "col": 2,
            "notes": "Swap (2,2) with (3,2) - Move: Down",
            "row": 2,
            "type": "Down"
        }
    ],
    "target": [
        [0,0,1,0,0],
        [0,0,1,0,0],
        [1,1,0,1,1],
        [0,0,1,0,0]
    ]
}

0 1 0 0 
0 1 0 0 
1 0 1 1 
0 1 0 0 
0 1 0 0 
到的执行计划
0 1 0 0 
0 1 0 0 
0 1 1 1 
0 1 0 0 
0 1 0 0 

{
    "count": 7,
    "finalState": [
        [0,1,0,0],
        [0,1,0,0],
        [0,1,1,1],
        [0,1,0,0],
        [0,1,0,0]
    ],
    "sorted": 0,
    "startCol": 0,
    "startRow": 0,
    "steps": [
        {
            "col": 0,
            "notes": "Swap (2,0) with (2,1) - Move: Right",
            "row": 2,
            "type": "Right"
        }
    ],
    "target": [
        [0,1,0,0],
        [0,1,0,0],
        [1,0,1,1],
        [0,1,0,0],
        [0,1,0,0]
    ]
}

执行计划使用示例

@SneakyThrows
public static void main(String[] args) {
    int[][] xxl = {
        {0, 0, 0, 0, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 1, 1, 0, 1, 1},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0},
    };
    // 获取执行计划
    List<Plan4Final> availablePlans = getAvailablePlans(xxl);
    System.out.println("可选执行计划数:"+availablePlans.size());

    // 循环执行计划 评估最佳执行计划
    for (Plan4Final plan : availablePlans) {
        List<PlanStep> steps = plan.getSteps();
        plan.setScore(plan.getCount()-3-steps.size());
        int[][] target = plan.getTarget();
        System.out.println(steps);
        printGrid(target);
    }
    Plan4Final bestPlan = availablePlans.stream().sorted(Comparator.comparingInt(Plan4Final::getScore).reversed()).findFirst().get();
    System.out.println("最佳执行计划");
    System.out.println(bestPlan);
    printGrid(bestPlan.getTarget());
}

可以看到生成了11个执行计划,通过消除元素个数和移动步数可以评估出最佳执行计划,例如(消除元素个数-移动步数)最大的,也可以根据获得的步数最多的来选出最佳执行计划

获得步数计算方式:(消除元素个数-3)X3的消除元素的等级幂次方,材料等级算0,比如材料消除时获得的步数为:(消除元素个数-3),1级元素消除时获得步数:(消除元素个数-3)X3,2级元素消除时获得步数:(消除元素个数-3)X3X3,以此类推

可选执行计划数:11
[PlanStep(row=1, col=2, type=Right, notes=Swap (1,2) with (1,3) - Move: Right)]
0 0 1 0 
1 1 0 1 
0 0 1 0 
0 0 1 0 

[PlanStep(row=0, col=2, type=Right, notes=Swap (0,2) with (0,3) - Move: Right)]
1 1 0 1 
0 0 1 0 
0 0 1 0 

[PlanStep(row=0, col=2, type=Down, notes=Swap (0,2) with (1,2) - Move: Down)]
0 0 1 
1 1 0 
0 0 1 
0 0 1 

[PlanStep(row=0, col=0, type=Down, notes=Swap (0,0) with (1,0) - Move: Down), PlanStep(row=0, col=1, type=Right, notes=Swap (0,1) with (0,2) - Move: Right), PlanStep(row=0, col=3, type=Down, notes=Swap (0,3) with (1,3) - Move: Down), PlanStep(row=1, col=1, type=Right, notes=Swap (1,1) with (1,2) - Move: Right), PlanStep(row=0, col=2, type=Right, notes=Swap (0,2) with (0,3) - Move: Right)]
0 0 1 0 
1 1 0 1 
0 0 1 0 

[PlanStep(row=1, col=0, type=Right, notes=Swap (1,0) with (1,1) - Move: Right)]
1 0 
0 1 
1 0 
1 0 

[PlanStep(row=1, col=0, type=Right, notes=Swap (1,0) with (1,1) - Move: Right)]
0 1 
1 0 
0 1 
0 1 

[PlanStep(row=0, col=0, type=Right, notes=Swap (0,0) with (0,1) - Move: Right)]
1 0 
0 1 
0 1 

[PlanStep(row=0, col=0, type=Right, notes=Swap (0,0) with (0,1) - Move: Right)]
0 1 
1 0 
1 0 

[PlanStep(row=1, col=0, type=Right, notes=Swap (1,0) with (1,1) - Move: Right)]
0 1 
1 0 
0 1 

[PlanStep(row=1, col=0, type=Right, notes=Swap (1,0) with (1,1) - Move: Right)]
1 0 
0 1 
1 0 

[PlanStep(row=0, col=0, type=Down, notes=Swap (0,0) with (1,0) - Move: Down)]
1 
0 
1 
1
最佳执行计划
Plan4Final(score=2, count=6, target=[[0, 0, 1, 0], [1, 1, 0, 1], [0, 0, 1, 0], [0, 0, 1, 0]], finalState=[[0, 0, 1, 0], [1, 1, 1, 0], [0, 0, 1, 0], [0, 0, 1, 0]], startRow=1, startCol=1, steps=[PlanStep(row=1, col=2, type=Right, notes=Swap (1,2) with (1,3) - Move: Right)])
0 0 1 0 
1 1 0 1 
0 0 1 0 
0 0 1 0

可以看到这里有11个执行计划,以lv0级的材料为例,3消得0分,4消得1分,5消得2分,6消得3分,7消得4分,这里可以看出得分lv0的分策略为消除元素个数-3

代码说明

这部分不重要,执行计划只需要生成一次,以后根据执行计划执行即可,感兴趣的可以继续往下看完整执行计划

生成执行计划

只需要运行main方法即可生产执行计划,共20036个执行计划,由于要大量的排列组合,这段代码比较耗时

package com.lxw.robot.ydxz.xxl.plus;

import com.alibaba.fastjson.JSON;
import com.lxw.robot.ydxz.xxl.ArraySwapper;
import com.lxw.robot.ydxz.xxl.entity.MinSubMatrix;
import com.lxw.robot.ydxz.xxl.entity.Plan4Final;
import com.lxw.robot.ydxz.xxl.entity.PlanDTO;
import com.lxw.robot.ydxz.xxl.entity.PlanStep;
import com.lxw.robot.ydxz.xxl.finalform.ArrayTransformPlus;
import com.lxw.robot.ydxz.xxl.finalform.Plan;
import lombok.SneakyThrows;
import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

@Slf4j
public class PlanGenerator {

    public static void main(String[] args) {
        // 生成可能的组合
        List<PlanDTO> planDTOS = generatePossibleCombinations();
        // 生成可能的计划
        List<Plan4Final> plan4Finals = generatePlan(planDTOS);
        generateFinalPlan(plan4Finals);
    }


    /**
     * 将original数组移动moves次后可能的组合
     * 1. 做了去重
     * 2. 排除了行和列包含连续三个1的组合
     * @param original
     * @param moves
     * @return
     */
    public static Set<int[][]> possibleCombinationsAfterMoved(int[][] original, int moves) {
        Set<String> tmps = new HashSet<>();
        swapDFS(original, moves, tmps);
        Set<int[][]> results = new HashSet<>();
        for (String tmp : tmps) {
            int[][] ints = JSON.parseObject(tmp, int[][].class);
            if (convertArrayToStrings(ints).stream().noneMatch(item->item.contains("111"))) {
                results.add(ints);
            }
        }
        return results;
    }

    private static void swapDFS(int[][] array, int moves, Set<String> results) {
        if (moves == 0) {
            results.add(JSON.toJSONString(deepCopy(array)));
            return;
        }

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                // Only consider moving 1s
                if (array[i][j] == 1) {
                    // Try swapping in all four directions
                    if (i > 0 && array[i - 1][j] == 0) swap(array, i, j, i - 1, j, moves, results); // Up
                    if (i < array.length - 1 && array[i + 1][j] == 0)
                        swap(array, i, j, i + 1, j, moves, results); // Down
                    if (j > 0 && array[i][j - 1] == 0) swap(array, i, j, i, j - 1, moves, results); // Left
                    if (j < array[i].length - 1 && array[i][j + 1] == 0)
                        swap(array, i, j, i, j + 1, moves, results); // Right
                }
            }
        }
    }

    private static void swap(int[][] array, int x1, int y1, int x2, int y2, int moves, Set<String> results) {
        // Swap elements
        int temp = array[x1][y1];
        array[x1][y1] = array[x2][y2];
        array[x2][y2] = temp;

        // Recursively call with one less move
        swapDFS(array, moves - 1, results);

        // Swap back to restore state
        array[x2][y2] = array[x1][y1];
        array[x1][y1] = temp;
    }

    private static int[][] deepCopy(int[][] original) {
        int[][] copy = new int[original.length][];
        for (int i = 0; i < original.length; i++) {
            copy[i] = original[i].clone();
        }
        return copy;
    }

    /**
     * 生成可能的组合
     * @return
     */
    private static List<PlanDTO> generatePossibleCombinations() {
        List<PlanDTO> planDTOS = new ArrayList<>();
        Set<String> set = new HashSet<>();
        // key为可消除元素的个数,value为可能的消除形态
        Map<Integer, List<int[][]>> allPossibleOriginals = getAllPossibleOriginal();
        for (Map.Entry<Integer, List<int[][]>> entry : allPossibleOriginals.entrySet()) {
            Integer count = entry.getKey();
            log.info("count:{}",count);
            // 消除形态
            List<int[][]> arrayList = entry.getValue();
            for (int[][] original : arrayList) {
                // 移动1到5次
                for (int i = 1; i < 5; i++) {
                    // 移动后可能的结果
                    long start = System.currentTimeMillis();
                    Set<int[][]> changes = possibleCombinationsAfterMoved(original, i);
                    for (int[][] changed : changes) {
                        PlanDTO planDTO = new PlanDTO();
                        planDTO.setCount(count);
                        planDTO.setOriginal(original);
                        planDTO.setChanged(changed);
                        MinSubMatrix minSubArray = GridSwap.getMinSubArray(changed,original);
                        int[][] originalMinSubMatrix = minSubArray.getOriginalMinSubMatrix();
                        int[][] changedMinSubMatrix = minSubArray.getChangedMinSubMatrix();
                        planDTO.setOriginalMinSubMatrix(originalMinSubMatrix);
                        planDTO.setChangedMinSubMatrix(changedMinSubMatrix);
                        // 根据改变后最小数组相同去重
                        if (set.add(JSON.toJSONString(changedMinSubMatrix))) {
                            // 获取执行计划 有可能找不到,例如1, 1, 0, 1, 1到0, 1, 1, 1, 1 移动过程中必然会出现三个连续111
                            List<String> list = ArrayTransformPlus.minSteps(changedMinSubMatrix, originalMinSubMatrix);
                            if (list == null) {
                                continue;
                            }
                            List<PlanStep> steps = list.stream().map(item -> JSON.parseObject(item, PlanStep.class)).collect(Collectors.toList());
                            planDTO.setSteps(steps);
                            planDTOS.add(planDTO);
                        }
                    }
                    long end = System.currentTimeMillis();
                    log.info("可消除元素数:{},移动{}次可能的个数:{},耗时:{}",count,i,changes.size(),end-start);
                }
            }
        }
        System.out.println("可能的组合数量:" + planDTOS.size());
        Plan.appendToFile(JSON.toJSONString(planDTOS), "src/main/resources/xxl/possible_combinations.json", false);
        return planDTOS;
    }

    /**
     * 生成可能的计划
     * @param planDTOS
     * @return
     */
    private static List<Plan4Final> generatePlan(List<PlanDTO> planDTOS) {
        List<Plan4Final> plans = new ArrayList<>();
        Set<String> tmp = new HashSet<>();
        System.out.println(planDTOS.size());
        for (PlanDTO planDTO : planDTOS) {
            int[][] originalMinSubMatrix = planDTO.getOriginalMinSubMatrix();
            int[][] changedMinSubMatrix = planDTO.getChangedMinSubMatrix();
            if (tmp.add(JSON.toJSONString(changedMinSubMatrix))) {
                Plan4Final plan4Final = new Plan4Final();
                plan4Final.setCount(planDTO.getCount());
                plan4Final.setTarget(changedMinSubMatrix);
                plan4Final.setFinalState(originalMinSubMatrix);
                plan4Final.setSteps(planDTO.getSteps());
                plans.add(plan4Final);
            }
        }
        System.out.println(plans.size());
        Plan.appendToFile(JSON.toJSONString(plans),"src/main/resources/xxl/possible_plans.json",false);
        return plans;
    }

    /**
     * 生成最终执行计划
     * 1. 去重
     * 2. 验证计划的正确性
     */
    @SneakyThrows
    private static void generateFinalPlan(List<Plan4Final> plans) {
        System.out.println("plans:"+plans.size());
        List<Plan4Final> ok = new ArrayList<>();
        List<Plan4Final> error =  new ArrayList<>();
        Set<String> okSet = new HashSet<>();
        Set<String> errorSet = new HashSet<>();
        for (Plan4Final plan : plans) {
            int[][] target = plan.getTarget();
            // 初始状态包含111
            if (PlanGenerator.convertArrayToStrings(target).stream().anyMatch(item->item.contains("111"))) {
                continue;
            }
            int[][] copy = JSON.parseObject(JSON.toJSONString(target), int[][].class);
            int[][] finalState = plan.getFinalState();
            boolean tmp = false;
            // 移动过程中包含111
            for (int i = 0; i < plan.getSteps().size(); i++) {
                PlanStep step = plan.getSteps().get(i);
                ArraySwapper.swapAdjacent(step.getRow(), step.getCol(), step.getType(), copy);
                for (String rowOrCol : PlanGenerator.convertArrayToStrings(copy)) {
                    // 最后一次移动前不能包含1
                    if (i<plan.getSteps().size()-1&&rowOrCol.contains("111")) {
                        tmp = true;
                        break;
                    }
                }
            }

            if (tmp) {
                continue;
            }
            if (JSON.toJSONString(finalState).equals(JSON.toJSONString(copy))) {
                if (okSet.add(JSON.toJSONString(plan))) {
                    ok.add(plan);
                }
            }else {
                if (errorSet.add(JSON.toJSONString(plan))) {
                    error.add(plan);
                }
            }
        }

        System.out.println("ok:"+ok.size());
        System.out.println("error:"+error.size());
        Plan.appendToFile(JSON.toJSONString(ok),"src/main/resources/xxl/ok.json",false);
        Plan.appendToFile(JSON.toJSONString(error),"src/main/resources/xxl/error.json",false);
    }

    /**
     * 由3,4,5,6,7个1组成的所有可能的6*6数组
     *
     * @return
     */
    public static Map<Integer, List<int[][]>> getAllPossibleOriginal() {
        long start = System.currentTimeMillis();
        Map<Integer, List<int[][]>> result = new HashMap<>();
        int[][] p7 = {
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 1, 1},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0},
        };
        buildPossibleOriginal(p7, 7, result);
        int[][] p6_1 = {
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 1, 1, 1, 1},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0},
        };
        buildPossibleOriginal(p6_1, 6, result);
        int[][] p5_1 = {
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 1, 1},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0},
        };
        buildPossibleOriginal(p5_1, 5, result);
        int[][] p5_2 = {
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 1, 1},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
        };
        buildPossibleOriginal(p5_2, 5, result);
        int[][] p5_3 = {
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 1, 1, 1, 0},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0},
        };
        buildPossibleOriginal(p5_3, 5, result);
        int[][] p4_1 = {
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 1, 1, 1, 1},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
        };
        buildPossibleOriginal(p4_1, 4, result);

        int[][] p3_1 = {
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 1, 1, 1, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0},
        };
        buildPossibleOriginal(p3_1, 3, result);
        long end = System.currentTimeMillis();
        log.info("获取原始数组耗时:{}",(end-start));
        return result;

    }

    /**
     * 构建可能的原始数组
     *
     * @param ints   二维数组
     * @param count  1的个数
     * @param result 最终结果
     */
    private static void buildPossibleOriginal(int[][] ints, int count, Map<Integer, List<int[][]>> result) {
        List<int[][]> arrayList = result.computeIfAbsent(count, k -> new ArrayList<>());
        int[][] rotate90Clockwise = GridSwap.rotate90Clockwise(ints);
        int[][] rotate180Clockwise = GridSwap.rotate180Clockwise(ints);
        int[][] rotate270Clockwise = GridSwap.rotate270Clockwise(ints);
        int[][] flipHorizontally = GridSwap.flipHorizontally(ints);
        int[][] flipVertically = GridSwap.flipVertically(ints);
        Set<String> set = new HashSet<>();
        if (set.add(JSON.toJSONString(ints))) {
            arrayList.add(ints);
        }
        if (set.add(JSON.toJSONString(rotate90Clockwise))) {
            arrayList.add(rotate90Clockwise);
        }
        if (set.add(JSON.toJSONString(rotate180Clockwise))) {
            arrayList.add(rotate180Clockwise);
        }
        if (set.add(JSON.toJSONString(rotate270Clockwise))) {
            arrayList.add(rotate270Clockwise);
        }
        if (set.add(JSON.toJSONString(flipVertically))) {
            arrayList.add(flipVertically);
        }
        if (set.add(JSON.toJSONString(flipHorizontally))) {
            arrayList.add(flipHorizontally);
        }
    }

    public static List<String> convertArrayToStrings(int[][] array) {
        List<String> resultSet = new ArrayList<>();
        // 转换每一行
        for (int[] row : array) {
            StringBuilder rowString = new StringBuilder();
            for (int num : row) {
                rowString.append(num);
            }
            resultSet.add(rowString.toString());
        }
        // 转换每一列
        for (int col = 0; col < array[0].length; col++) {
            StringBuilder colString = new StringBuilder();
            for (int[] row : array) {
                colString.append(row[col]);
            }
            resultSet.add(colString.toString());
        }
        return resultSet;
    }

}

实体类说明

最终执行计划

@Data
@Accessors(chain = true)

/**
 * 最终执行计划
 */
public class Plan4Final {
    /**
     * 元素类型
     */
    private String type;
    /**
     * 可消除元素个数
     */
    private int count;
    /**
     * 寻找目标
     */
    private int[][] target;

    /**
     * 移动后的最终状态
     */
    private int[][] finalState;
    /**
     * target在大数组中的行
     */
    private int startRow;
    /**
     * target在大数组中的列
     */
    private int startCol;

    /**
     * 移动步骤/执行计划
     */
    private List<PlanStep> steps;

    /**
     * 排序
     */
    private int sorted;

}

说明:

target 需要消除的区域,例如

通过移动后的最终状态,例如

移动步骤/执行计划

@Data
public class PlanStep {
    /**
     * 行 下标从0开始
     */
    private int row;
    /**
     * 列 下标从0开始
     */
    private int col;
    /**
     * 移动类型:Right,Down,Left,Up
     */
    private String type;
    /**
     * 那个元素和那个元素进行的交换,仅仅只是记录一下,可忽略
     */
    private String notes;
}

例如将本示例中target的执行计划为[{“col”:2,“notes”:“Swap (2,2) with (2,3) - Move: Right”,“row”:2,“type”:“Right”}],即将target中的第二行第二列中的元素向右移动一次即可得到finalState

执行计划生成过程中的中间类

@Data
@Accessors(chain = true)
public class PlanDTO {
    /**
     * 元素个数(不再关注)
     */
    @Deprecated
    private int count;
    /**
     * 移动步数(不再关注)
     */
    @Deprecated
    private int step;
    /**
     * 原始数组(不再关注)
     */
    @Deprecated
    private int[][] original;
    /**
     * 移动count步的数组(不再关注)
     */
    @Deprecated
    private int[][] changed;

    /**
     * 回到原始状态的步数(不再关注)
     */
    @Deprecated
    private int recoverStep;

    /**
     * 移动后数组的最小子数组(关注)
     */
    private int[][] changedMinSubMatrix;

    /**
     * 移动后数组的最小子数组 对应的原始数组区域 (关注)
     */
    private int[][] originalMinSubMatrix;

    /**
     * 移动步骤/执行计划
     */
    private List<PlanStep> steps;

    /**
     * 执行后预期增加的步数(因为移动过程中导致其他位置消除,实际可能会多)
     */
    private int acquiredStepCount;
}

生成消除前形态

移动x步1生成出的所有组合,排出掉结果以及移动过程中有连续3个或以上1的结果,即移动后的结果通过x步移动,生成消除形态,且移动过程中没有3个或以上1

比如移动7连1步只有1中结果

0 0 0 0 0 0 
0 0 0 1 0 0 
0 1 1 0 1 1 
0 0 0 1 0 0 
0 0 0 1 0 0 
0 0 0 0 0 0

获取最小区域

获取消除前形态中包含所有1的最小区域,和这个消除前形态对应的消除形态中对应的区域,例如7连消除前包含所有1的最小区域

对应在7连中的区域

生成最小区域的代码

/**
 *
 * @param changed 消除前形态的二维数组
 * @param original 消除形态的二维数组
 * @return
 */
public static MinSubMatrix getMinSubArray(int[][] changed,int[][] original) {
    int[] minMax = findMinMaxIndices(changed);
    int minRow = minMax[0];
    int maxRow = minMax[1];
    int minCol = minMax[2];
    int maxCol = minMax[3];

    // 提取子数组
    int[][] changedSubArray = new int[maxRow - minRow + 1][maxCol - minCol + 1];
    int[][] originalSubArray = new int[maxRow - minRow + 1][maxCol - minCol + 1];
    for (int i = minRow; i <= maxRow; i++) {
        for (int j = minCol; j <= maxCol; j++) {
            changedSubArray[i - minRow][j - minCol] = changed[i][j];
            originalSubArray[i - minRow][j - minCol] = original[i][j];
        }
    }
    MinSubMatrix minSubMatrix = new MinSubMatrix();
    minSubMatrix.setChangedMinSubMatrix(changedSubArray);
    minSubMatrix.setOriginalMinSubMatrix(originalSubArray);
    return minSubMatrix;
}

private static int[] findMinMaxIndices(int[][] array) {
    int minRow = Integer.MAX_VALUE, maxRow = Integer.MIN_VALUE;
    int minCol = Integer.MAX_VALUE, maxCol = Integer.MIN_VALUE;

    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[i].length; j++) {
            if (array[i][j] == 1) {
                minRow = Math.min(minRow, i);
                maxRow = Math.max(maxRow, i);
                minCol = Math.min(minCol, j);
                maxCol = Math.max(maxCol, j);
            }
        }
    }
    return new int[]{minRow, maxRow, minCol, maxCol};
}

验证计划的正确定

对消除前形态最小区域按照执行计划移动,判断移动后的结果时候和消除形态相等,如果相等说明执行计划ok

验证执行计划的代码

String s = new String(Files.readAllBytes(Paths.get("src/main/resources/xxl/plans.json")));
List<Plan4Final> plans = JSON.parseArray(s, Plan4Final.class);
for (Plan4Final plan : plans) {
    int[][] target = plan.getTarget();
    int[][] finalState = plan.getFinalState();
    for (PlanStep step : plan.getSteps()) {
        ArraySwapper.swapAdjacent(step.getRow(), step.getCol(), step.getType(), target);
    }
    if (!JSON.toJSONString(finalState).equals(JSON.toJSONString(target))) {
        System.out.println("执行计划不对");
    }
}

数组移动类

package com.lxw.robot.xxl;

public class ArraySwapper {

    public static void swapAdjacent(int row, int col, String direction, int[][] array) {
        int rows = array.length;
        int cols = array[0].length;

        // 定义相邻元素的偏移量
        int newRow = row;
        int newCol = col;

        switch (direction) {
            case "Right":
                newCol++;
                break;
            case "Down":
                newRow++;
                break;
            case "Left":
                newCol--;
                break;
            case "Up":
                newRow--;
                break;
            default:
                System.out.println("Invalid direction");
                return;
        }

        // 检查新的坐标是否在数组范围内
        if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
            // 交换元素
            int temp = array[row][col];
            array[row][col] = array[newRow][newCol];
            array[newRow][newCol] = temp;
        } else {
            System.out.println("Swap out of bounds");
        }
    }

    public static void printArray(int[][] array) {
        for (int[] row : array) {
            for (int num : row) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] array = {
                {0, 0, 0, 0, 0, 0},
                {0, 0, 0, 1, 0, 0},
                {0, 1, 1, 0, 1, 1},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0},
        };

        System.out.println("Before swap:");
        printArray(array);

        // 调用交换方法
        swapAdjacent(1, 3, "Down", array);

        System.out.println("After swap:");
        printArray(array);
    }
}