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

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 同一水平线上

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

代码：

/// <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 同一竖直直线上

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

代码：

/// <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 一个拐角检测

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

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

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

 /// <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.3 两个拐角检测

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

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

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

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

代码：

/// <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