连连看消除算法和最佳路径推荐

淩亂°似流年 2022-12-30 08:15 99阅读 0赞

## 1.连连看可以消除的规则 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXlpbmdodWk1MjM_size_16_color_FFFFFF_t_70][]

1.1 图A中出现在同一条直线无障碍物的圈圈可以消除。

1.2 图B中两个圈圈可以通过一次转弯消除。

1.3 图C和图D中可以通过两次转弯消除两个圈圈。

已知一个接口可以判断坐标 （x,y）上有障碍物：

/// <summary>
        /// 判断是否有障碍物
        /// </summary>
        /// <param name="x">X坐标</param> 
        /// <param name="y">Y坐标</param>
        /// <param name="y">Y坐标</param>
        /// <returns>是否有障碍物</returns>
        private static bool isBlocked(int x, int y, int[][] obstaclesArray) {
            
            //取出坐标位置的点 并且值不小于0 就是有障碍物
            if (obstaclesArray.Length > y && y >= 0) {
                if (obstaclesArray[y].Length > x && x >= 0)
                {
                    int tmp = obstaclesArray[y][x];
                    if (obstaclesArray[y][x] >= 0)
                    {
                        return true;
                    }
                }
            }
            return false;
        }
    
        /// <summary>
        /// 求两个整数的最小值
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <returns></returns>
        private static int min(int x, int y) {
    
            return (x < y) ? (x) : (y);
    
        }
    
        /// <summary>
        /// 求两个整数的最大值
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <returns></returns>
        static int max(int x, int y)
        {
            return (x > y) ? (x) : (y);
        }

## 2.两个坐标点的位置情况 ##

### 2.1 同一直线上 ###

2.1.1 同一水平线上

![20201224165829760.png][]

水平检测就是检测是否是同一个点，同时满足两者水平方向之间没有障碍物

代码：

/// <summary>
        /// 水平检测两点之间是否可以连接消除
        /// </summary>
        /// <param name="x1">第一个点的横坐标</param>
        /// <param name="y1">第一个点的纵坐标</param>
        /// <param name="x2">第二个点的横坐标</param>
        /// <param name="y2">第二个点的纵坐标</param>
        /// <returns>水平方向的两点是否可以连接消除</returns>
        private static bool horizon(int x1, int y1, int x2, int y2, int[][] obstaclesArray)
        {
            if (x1 == x2 && y1 == y2)
            {
                return false;
            }
    
            if (y1 != y2)
            {
                return false;
            }
            
            int start_x = min(x1, x2);
            int end_x = max(x1, x2);
            //如果两者相邻 可以消除
            if (start_x + 1 == end_x) {
                return true;
            }
            //判断直线中间是否有障碍物
            for (int i = start_x+1; i < end_x; i++)
            {
                if (isBlocked(i, y1,obstaclesArray))
                {
                    return false;
                }
            }
    
            return true;
        }

2.1.2 同一竖直直线上

![20201224170017718.png][]

竖直检测就是检测是否是同一个点，同时满足两者竖直方向之间没有障碍物

代码：

/// <summary>
        ///  一个拐角是否可以连接检测
        /// </summary>
        /// <param name="x1">第一个点的横坐标</param>
        /// <param name="y1">第一个点的纵坐标</param>
        /// <param name="x2">第二个点的横坐标</param>
        /// <param name="y2">第二个点的纵坐标</param>
        /// <param name="location">连接的节点</param>
        /// <returns>一个拐角是否可以满足连接</returns>
        ///
        private static bool turn_once(int x1, int y1, int x2, int y2,out (int,int) location,int[][] obstaclesArray)
        {
            location = (0,0);
            if (x1 == x2 && y1 == y2)
            {
                return false;
            }
            
    
            int c_x = x1, c_y = y2;
            int d_x = x2, d_y = y1;
            bool ret = false;
    
            if (!isBlocked(c_x, c_y,obstaclesArray))
            {
                //两个坐标 所在横竖四条直线交叉中的第一个交点检测 
                ret |= vertical(x1, y1, c_x, c_y,obstaclesArray) && horizon(c_x, c_y, x2, y2,obstaclesArray);
                if (ret) {
                    location = (c_x, c_y);
                }
            }
            else {
                //两个坐标 所在横竖四条直线交叉中的另一个交点检测 
                if (!isBlocked(d_x, d_y,obstaclesArray))
                {
                    ret |= horizon(x1, y1, d_x, d_y,obstaclesArray) && vertical(d_x, d_y, x2, y2,obstaclesArray);
                    if (ret) {
                        location = (d_x, d_y);
                    }
                }
            }
            if (ret)
            {
                return true;
            }
    
            return false;
        }

### 2.2 一个拐角检测 ###

![20201224170146857.png][]

一个拐角检测可以分解为一个水平检测和垂直检测，两个检测同时满足的时候，便可以通过一个拐角连接两点。一个拐角检测 = 水平检测 && 垂直检测。

A 点至 B 点能否连接可转化为满足任意一点：

1.  A 点至 C 点的垂直检测，以及 C 点至 B 点的水平检测；
2.  A 点至 D 点的水平检测，以及 D 点至 B 点的垂直检测。

### 2.3 两个拐角检测 ###

两个拐角检测可以分解为一个拐角检测和水平检测或者垂直检测。

即：两个拐角检测 = 一个拐角检测 && （水平检测 || 竖直检测）

水平和竖直分别穿过AB公有四条线，扫描直线上所有不包含AB的点，看是否存在一个点C，满足任意一项：

1.  A 点至 C 点通过水平或垂直检测，C 点至 B 点可通过一个拐角连接。（图中用 C 表示）
2.  A 点至 C 点可通过一个拐角连接，C 点至 B 点通过水平或垂直连接。（图中用 C 下划线表示）

![2020122417033534.png][]

代码：

/// <summary>
        /// 两个拐点连接检测
        /// </summary>
        /// <param name="x1">第一个点的横坐标</param>
        /// <param name="y1">第一个点的纵坐标</param>
        /// <param name="x2">第二个点的横坐标</param>
        /// <param name="y2">第二个点的纵坐标</param>
        /// <param name="maxX">连连看布局的列数</param>
        /// <param name="location0">最优解第一个拐弯的节点</param>
        /// <param name="location1">最优解第二个拐弯的节点</param>
        /// <param name="maxY">连连看布局的行数</param>
        /// <returns>两个拐点是否可以连接检测结果</returns>
       private static bool turn_twice_best(int x1, int y1, int x2, int y2,int maxX,int maxY,out (int,int) location0,out (int,int) location1, int[][] obstaclesArray)
        {
            location0 = (0, 0);
            location1 = (0, 0);
            if (x1 == x2 && y1 == y2)
            {
                return false;
            }
            
            int start_y = min(y1, y2);
            
            
            int end_y = max(y1, y2);
            
           var locTmp0 = (0,0);
           var locTmp1 = (0,0);
            
            for (int j = -1; j <= maxY; j++)
            {
                for (int i = -1; i <= maxX; i++)
                {
                    if (i != x1 && i != x2 && j != y1 && j != y2)
                    {
                        continue;
                    }
    
                    if ((i == x1 && j == y1) || (i == x2 && j == y2))
                    {
                        continue;
                    }
    
                    if (isBlocked(i, j,obstaclesArray))
                    {
                        continue;
                    }
           
                    // //拆开校验
                    // bool turnOnce = turn_once(x1, y1, i, j, out location0, obstaclesArray);
                    // bool horizonTmp = horizon(i, j, x2, y2, obstaclesArray);
                    // bool verticalTmp = vertical(i, j, x2, y2, obstaclesArray);
                    //
                    // if (turnOnce && (horizonTmp || verticalTmp))
                    // {
                    //     
                    // }
                    // else
                    // {
                    //     bool turnOnce1 = turn_once(i, j, x2, y2,out location1,obstaclesArray);
                    //     bool horizonTmp1 = horizon(x1, y1, i, j,obstaclesArray);
                    //     bool verticalTmp1 = vertical(x1, y1, i, j,obstaclesArray);
                    //
                    //     
                    // }
                    
                    bool canRemoveResult = turn_twice_one(x1, y1, i,j,x2, y2,out locTmp0,  out locTmp1, obstaclesArray);
                    if (canRemoveResult)
                    {
                        if (location0.Item1 ==0 && location0.Item2 == 0 && location1.Item1 == 0 && location1.Item2 == 0)
                            {
                                location0 = locTmp0;
                                location1 = locTmp1;
                            }
                            else
                            {
                                var pathCount0 = pathCount(x1, y1, x2, y2, location0, location1);
                                var pathCount1 = pathCount(x1, y1, x2, y2, locTmp0, locTmp1);
                                if (pathCount1 < pathCount0)
                                {
                                    location0 = locTmp0;
                                    location1 = locTmp1;
                                }
                            }
                    }
                    
                    canRemoveResult = turn_twice_two(x1, y1, i,j,x2, y2,out locTmp0,  out locTmp1, obstaclesArray);
                    if (canRemoveResult)
                    {
                        if (location0.Item1 ==0 && location0.Item2 == 0 && location1.Item1 == 0 && location1.Item2 == 0)
                            {
                                location0 = locTmp0;
                                location1 = locTmp1;
                            }
                            else
                            {
                                var pathCount0 = pathCount(x1, y1, x2, y2, location0, location1);
                                var pathCount1 = pathCount(x1, y1, x2, y2, locTmp0, locTmp1);
                                if (pathCount1 < pathCount0)
                                {
                                    location0 = locTmp0;
                                    location1 = locTmp1;
                                }
    
                            }
                    }
                }
               
            }
            return (location0.Item1 != 0 || location0.Item2 != 0 || location1.Item1 != 0 || location1.Item2 != 0);
        }
    
        /// <summary>
        /// 求折线的总路径数量
        /// </summary>
        /// <param name="x1">开始点的横坐标</param>
        /// <param name="y1">开始点的纵坐标</param>
        /// <param name="x2">结束点的横坐标</param>
        /// <param name="y2">结束点的纵坐标</param>
        /// <param name="location0">第一个拐角点</param>
        /// <param name="location1">第二个拐角点</param>
        /// <returns></returns>
        private static int pathCount(int x1, int y1, int x2, int y2, (int, int) location0, (int, int) location1)
        {
            var count = 0;
            count += pointPointLength((x1, y1), location0);
            count += pointPointLength(location0, location1);
            count += pointPointLength(location1, (x2, y2));
            return count;
        }
        /// <summary>
        /// 求两个点的横纵坐标差绝对值之和
        /// </summary>
        /// <param name="location0"></param>
        /// <param name="location1"></param>
        /// <returns></returns>
        private static int pointPointLength((int, int) location0, (int, int) location1)
        {
            return System.Math.Abs(location0.Item1 - location1.Item1) + System.Math.Abs(location0.Item2 - location1.Item2);
        }
        /// <summary>
        /// 第一种双折方式是否可以消除
        /// </summary>
        /// <param name="x1">第一个点横坐标</param>
        /// <param name="y1">第一个点的纵坐标</param>
        /// <param name="i">选中的点横坐标</param>
        /// <param name="j">选中点的纵坐标</param>
        /// <param name="x2">第二个点的横坐标</param>
        /// <param name="y2">第二个点的纵坐标</param>
        /// <param name="location0">第一个折点坐标</param>
        /// <param name="location1">第二个折点坐标</param>
        /// <param name="obstaclesArray">原始数据矩阵</param>
        /// <returns>是否可以消除</returns>
        private static bool turn_twice_one(int x1, int y1, int i, int j,int x2, int y2, out (int, int) location0,
            out (int, int) location1, int[][] obstaclesArray)
        {
            location0 = (0, 0);
            location1 = (0, 0);
            if (turn_once(x1, y1, i, j,out location0,obstaclesArray) && (horizon(i, j, x2, y2,obstaclesArray) || vertical(i, j, x2, y2,obstaclesArray)))
            {
                location1 = (i, j);
                return true;
            }
            return false;
        }
        /// <summary>
        /// 第二种双折方式是否可以消除
        /// </summary>
        /// <param name="x1">第一个点横坐标</param>
        /// <param name="y1">第一个点的纵坐标</param>
        /// <param name="i">选中的点横坐标</param>
        /// <param name="j">选中点的纵坐标</param>
        /// <param name="x2">第二个点的横坐标</param>
        /// <param name="y2">第二个点的纵坐标</param>
        /// <param name="location0">第一个折点坐标</param>
        /// <param name="location1">第二个折点坐标</param>
        /// <param name="obstaclesArray">原始数据矩阵</param>
        /// <returns>是否可以消除</returns>
        private static bool turn_twice_two(int x1, int y1,int i,int j, int x2, int y2, out (int, int) location0,
            out (int, int) location1, int[][] obstaclesArray)
        {
            location0 = (0, 0);
            location1 = (0, 0);
            if (turn_once(i, j, x2, y2,out location1,obstaclesArray) && (horizon(x1, y1, i, j,obstaclesArray) || vertical(x1, y1, i, j,obstaclesArray)))
            {
                location0 = (i, j);
                return true;
            }
            return false;
        }

## 3 检测两个点是否可以消除 ##

两个点是否可以连接消除的判断就是对两个点判断是否满足步骤2 中的某一种情况。

满足消除条件之后，给出建议路径。

// ReSharper disable Unity.PerformanceAnalysis
        /// <summary>
        /// 检测两点是否可以消除
        /// </summary>
        /// <param name="x1">第一个点的横坐标</param>
        /// <param name="y1">第一个点的纵坐标</param>
        /// <param name="x2">第二个点的横坐标</param>
        /// <param name="y2">第二个点的纵坐标</param>
        /// <param name="obstaclesArray">布局的矩阵</param>
        /// <param name="result">可消除节点路径</param>
        /// <returns>是否可以消除</returns>
        public static  bool isCanRemove(int x1, int y1, int x2, int y2, int[][] obstaclesArray, out List<(int, int)> result)
        {
            // string startEndPointStr = $"开始点消除方法开始  :({x1},{y1}), 结束点:({x2},{y2})";
            bool ret = false;
            result = new List<(int, int)>();
            
            // 检测行数是否大于0 并且 每一行的元素个数都相等
            int rows = obstaclesArray.Length;
            int columnsFirst = 0;
            if (rows > 0)
            {
                columnsFirst = obstaclesArray[0].Length;
                if (rows > 1) {
                    for (int index = 0; index < rows; index++)
                    {
                        int columns = obstaclesArray[index].Length;
                        if (columnsFirst != columns)
                        {
                            return false;
                        }
                    }
                }
            }
            else {
                return false;
            }
            // 横向检测
            ret = horizon(x1, y1, x2, y2,obstaclesArray);
            if (ret)
            {
                result.Add((x1, y1));
                result.Add((x2, y2));
                return true;
            }
            //竖向检测
            ret = vertical(x1, y1, x2, y2,obstaclesArray);
            if (ret)
            {
                result.Add((x1, y1));
                result.Add((x2, y2));
                return true;
            }
            //一个拐角检测
            ret = turn_once(x1, y1, x2, y2,out (int,int) location,obstaclesArray);
            if (ret)
            {
                result.Add((x1, y1));
                result.Add(location);
                result.Add((x2, y2));
                return true;
            }
            // 两个拐角检测
            ret = turn_twice_best(x1, y1, x2, y2, columnsFirst, rows,out (int,int) location0,out (int,int) location1,obstaclesArray);
            if (ret)
            {
                result.Add((x1, y1));
                result.Add(location0);
                result.Add(location1);
                result.Add((x2, y2));
                return true;
            }
            return false;
        }

4 对消消看初始数据给出建议

给出连连看初始数据，判断是否可以匹配消除并在可以消除的情况下给出消除路径。

/// <summary>
        /// 是否有可以提示的消除路径
        /// </summary>
        /// <param name="obstaclesArray">障碍物二维数组 元素是整型 数据 小于0表示没有障碍物</param>
        /// <param name="result">可以连接的节点</param>
        /// <returns></returns>
        public static bool isCanPrompt(int[][] obstaclesArray, out List<(int, int)> result) {
    
            result = new List<(int, int)>();
            // 检测行数是否大于0 并且 每一行的元素个数都相等
            int rows = obstaclesArray.Length;
            int columnsFirst = 0;
            if (rows > 0)
            {
                columnsFirst = obstaclesArray[0].Length;
                if (rows > 1)
                {
                    for (int index = 0; index < rows; index++)
                    {
                        int columns = obstaclesArray[index].Length;
                        if (columnsFirst != columns)
                        {
                            return false;
                        }
                    }
                }
            }
            else
            {
                return false;
            }
    
            Dictionary<int, List<(int, int)>> typeDic = new Dictionary<int, List<(int,int)>>();
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columnsFirst; j++) {
                    int type = obstaclesArray[i][j];
                    if (type >= 0)
                    {
                        List<(int, int)> array = new List<(int, int)>();
                        typeDic.TryGetValue(type, out array);
                        if (array == null) {
                            array = new List<(int, int)>();
                        }
                        if (array != null) {
                            array.Add((j, i));
                        }
                        typeDic[type] = array;
                    }
                }
            }
    
            Dictionary<int, List<(int, int)>>.ValueCollection valueColl = typeDic.Values;
            //遍历值的集合
            foreach (List <(int, int)> list in valueColl)
            {
                if (list.Count > 0) {
                    for (int i= 0;i < list.Count;i ++) {
                        for (int j = i+1; j < list.Count;j++) {
                            (int, int) startPosition = list[i];
                            (int, int) endPosition = list[j];
                            bool canRemove = isCanRemove(startPosition.Item1, startPosition.Item2, endPosition.Item1, endPosition.Item2, obstaclesArray,out result);
                            if (canRemove) {
                                return true;
                            }
                        }
                    }
                }
            }
            return false;
        }

参考链接：[https://blog.csdn.net/qq\_41551359/article/details/82983513][https_blog.csdn.net_qq_41551359_article_details_82983513]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXlpbmdodWk1MjM_size_16_color_FFFFFF_t_70]: /images/20221120/58999db270d6445c967f51ab1e91521a.png
[20201224165829760.png]: /images/20221120/6a9a03254a2b4b64a3ee13fca3cf2c23.png
[20201224170017718.png]: /images/20221120/b5aad3ca8b06499789dff21680ad691d.png
[20201224170146857.png]: https://img-blog.csdnimg.cn/20201224170146857.png
[2020122417033534.png]: https://img-blog.csdnimg.cn/2020122417033534.png
[https_blog.csdn.net_qq_41551359_article_details_82983513]: https://blog.csdn.net/qq_41551359/article/details/82983513