2折的时候输出路径时取最短路径

using System;  
using System.Drawing;  
using System.Collections;  
  
namespace LLK.AI  
{  
    /**//// <summary>  
    /// 连连看的连线算法  
    /// 作者：随飞  
    /// 编写日期：2005-6-6  
    /// 首先是 x to x ,这个是横向比较直连  
    /// 然后是 y to y ,这个是竖向比较直连  
    ///   
    /// 然后是 1个折点  
    /// 算法很简单;比如  
    /// 7x3的  
    /// 0001000  
    /// 0000000  
    /// 0000001  
    ///   
    /// p1 是 3,0  
    /// p2 是 6,2  
    ///   
    /// 那么折点是  
    /// 000100x  
    /// 0000000  
    /// 000x001  
    /// 折点1是 6,0 ,折点2是 3,2  
    /// 注意这个值和p1,p2的比较,是不是很简单,折点出来了,就可以比较x/y直线了,如果成立则通过.  
    ///   
    /// 2折就复杂一点,在上面都不成立后,  
    /// 一次根据上下左右分别按1折算法再比较即可.  
    /// </summary>  
      
    public class TestPath  
    {  
        int pathPointCount = 0;  
        ArrayList PathRecord = new ArrayList();  
        int[,] map = null; //地图  
        Point startPos;    //起点  
        Point endPos;    //终点  
          
        public TestPath(){;}  
  
        public TestPath(Point StartPos,Point EndPos,int[,] Map)  
        {  
            this.startPos = StartPos;  
            this.endPos = EndPos;  
            this.map = Map;  
        }  
  
  
        private void EmptyPathRecord()  
        {  
            PathRecord.Clear();  
            PathRecord.TrimToSize();  
            PathRecord.Add(this.startPos);  
            PathRecord.Add(this.endPos);  
        }  
  
        private bool IsEmptyPoint(Point p)  
        {  
            return this.map[p.X,p.Y]==0;  
        }  
  
        private bool CheckHorizontal(Point p1,Point p2)  
        {  
            return this.CheckHorizontal(p1,p2,false);  
        }  
  
        private bool CheckHorizontal(Point p1,Point p2, bool isAddPath)  
        {  
            //检查水平，x位移,y相同  
  
            Point sp = p1.X<p2.X?p1:p2;  
            Point ep = p2.X<p1.X?p1:p2;  
  
            for(int x =sp.X+1;x<ep.X;x++)  
            {  
                //允许记录  
                if(isAddPath)  
                {  
                    this.PathRecord.Add(new Point(x,p1.Y));  
                }  
                //不可通过  
                if(map[x,p1.Y]!=0)  
                    return false;  
            }  
  
            return true;  
        }  
  
        private bool CheckVertical(Point p1,Point p2)  
        {  
            return CheckVertical(p1,p2,false);  
        }  
  
        private bool CheckVertical(Point p1,Point p2, bool isAddPath)  
        {  
            //检查垂直，y位移,x相同  
  
            Point sp = p1.Y<p2.Y?p1:p2;  
            Point ep = p2.Y<p1.Y?p1:p2;  
  
            for(int y =sp.Y+1; y<ep.Y; y++)  
            {  
                //允许记录  
                if(isAddPath)  
                {  
                    this.PathRecord.Add(new Point(p1.X,y));  
                }  
                //不可通过  
                if(map[p1.X,y]!=0)  
                    return false;  
            }  
  
            return true;  
        }  
  
        private bool CheckOneCorner(Point p1,Point p2)  
        {  
            return CheckOneCorner(p1,p2,true,true);  
        }  
        private bool CheckOneCorner(Point p1,Point p2, bool isAddPath, bool isClear)  
        {  
            //计算夹角  
  
            //取起始x  
            Point CrossStart;  
            Point CrossEnd;  
  
            if(p1.X<p2.X)  
            {  
                CrossStart = p1;  
                CrossEnd = p2;  
            }  
            else  
            {  
                CrossStart = p2;  
                CrossEnd = p1;  
            }  
          
            //交叉点X  
            //正向  
            Point CrossX ;  
            //交叉点Y  
            //反向  
            Point CrossY ;  
  
            if(CrossStart.Y<CrossEnd.Y)  
            {  
                CrossX = new Point(  
                    Math.Max(CrossStart.X,CrossEnd.X),  
                    Math.Min(CrossStart.Y,CrossEnd.Y)  
                    );  
                CrossY = new Point(  
                    Math.Min(CrossStart.X,CrossEnd.X),  
                    Math.Max(CrossStart.Y,CrossEnd.Y)  
                    );  
            }  
            else  
            {  
                CrossX = new Point(  
                    Math.Min(CrossStart.X,CrossEnd.X),  
                    Math.Min(CrossStart.Y,CrossEnd.Y)  
                    );  
                CrossY = new Point(  
                    Math.Max(CrossStart.X,CrossEnd.X),  
                    Math.Max(CrossStart.Y,CrossEnd.Y)  
                    );  
            }  
  
            //检查交叉点是否为可通过  
            if(!this.IsEmptyPoint(CrossX) && !this.IsEmptyPoint(CrossY))  
                return false;  
  
            //检查交叉点X  
            if(this.IsEmptyPoint(CrossX))  
            {  
                //检查横位  
                if(CrossStart.Y<CrossEnd.Y)  
                {  
                    //方向为~|  
                    if(this.CheckHorizontal(CrossStart,CrossX) && this.CheckVertical(CrossX,CrossEnd))  
                    {      
                        //允许清空  
                        if(isClear)  
                        {  
                            this.EmptyPathRecord();  
                        }  
                        //允许记录  
                        if(isAddPath)  
                        {  
                            this.PathRecord.Add(CrossX);//记录当前交叉点  
                        }                              
                        return (this.CheckHorizontal(CrossStart,CrossX,true) && this.CheckVertical(CrossX,CrossEnd,true));                           
                    }  
                    //不跳出，留下一点检测  
                }  
                else  
                {  
                    //方向为|~  
                    if(this.CheckHorizontal(CrossX,CrossEnd) && this.CheckVertical(CrossX,CrossStart))  
                    {  
                        //允许清空  
                        if(isClear)  
                        {  
                            this.EmptyPathRecord();  
                        }  
                        //允许记录  
                        if(isAddPath)  
                        {  
                            this.PathRecord.Add(CrossX);//记录当前交叉点  
                        }  
                        return (this.CheckHorizontal(CrossX,CrossEnd,true) && this.CheckVertical(CrossX,CrossStart,true));  
                    }  
                    //不跳出，留下一点检测  
                }   
            }  
  
            //检查交叉点Y  
            if(this.IsEmptyPoint(CrossY))  
            {  
                //检查竖位              
                if(CrossStart.Y<CrossEnd.Y)  
                {  
                    //方向为|_  
                    if(this.CheckVertical(CrossStart,CrossY) && this.CheckHorizontal(CrossY,CrossEnd))  
                    {  
                        //允许清空  
                        if(isClear)  
                        {  
                            this.EmptyPathRecord();  
                        }  
                        //允许记录  
                        if(isAddPath)  
                        {  
                            this.PathRecord.Add(CrossY);//记录当前交叉点  
                        }  
                        return (this.CheckVertical(CrossStart,CrossY,true) && this.CheckHorizontal(CrossY,CrossEnd,true));  
                    }  
                }  
                else  
                {  
                    //方向_|  
                    if(this.CheckVertical(CrossEnd,CrossY) && this.CheckHorizontal(CrossY,CrossStart))  
                    {  
                        //允许清空  
                        if(isClear)  
                        {  
                            this.EmptyPathRecord();  
                        }  
                        //允许记录  
                        if(isAddPath)  
                        {  
                            this.PathRecord.Add(CrossY);//记录当前交叉点  
                        }  
                        return (this.CheckVertical(CrossEnd,CrossY,true) && this.CheckHorizontal(CrossY,CrossStart,true));  
                    }  
                }  
  
            }  
            return false; //全部不成立,留给2次折点检测  
  
        }  
  
        private bool CheckTwoCornerLeft(Point p1,Point p2,bool isAddPath)  
        {  
            //左  
            //清空记录  
            this.EmptyPathRecord();  
            for(int x = p1.X -1; x>-1; x--)  
            {  
                if(this.map[x,p1.Y]!=0)  
                    return false;  
                //允许记录  
                if(isAddPath)  
                {  
                    this.PathRecord.Add(new Point(x,p1.Y));  
                }  
  
                //不允许清空  
                if(this.CheckOneCorner(new Point(x,p1.Y),p2,false,false))  
                {  
                    return this.CheckOneCorner(new Point(x,p1.Y),p2,isAddPath,false);  
                }  
            }  
  
            return false;  
        }  
  
        private bool CheckTwoCornerRight(Point p1,Point p2,bool isAddPath)  
        {  
            //右  
            //清空记录  
            this.EmptyPathRecord();  
            for(int x = p1.X +1; x<this.map.GetLength(0); x++)  
            {  
                if(this.map[x,p1.Y]!=0)  
                    return false;  
                //允许记录  
                if(isAddPath)  
                {  
                    this.PathRecord.Add(new Point(x,p1.Y));  
                }  
  
                //不允许清空  
                if(this.CheckOneCorner(new Point(x,p1.Y),p2,false,false))  
                {  
                    return this.CheckOneCorner(new Point(x,p1.Y),p2,isAddPath,false);  
                }  
            }   
            return false;  
        }  
  
        private bool CheckTwoCornerUp(Point p1,Point p2,bool isAddPath)  
        {  
            //上  
            //清空记录  
            this.EmptyPathRecord();  
            for(int y = p1.Y -1; y>-1; y--)  
            {  
                if(this.map[p1.X,y]!=0)  
                    return false;  
                //允许记录  
                if(isAddPath)  
                {  
                    this.PathRecord.Add(new Point(p1.X,y));  
                }  
  
                //不允许清空  
                if(this.CheckOneCorner(new Point(p1.X,y),p2,false,false))  
                {  
                    return this.CheckOneCorner(new Point(p1.X,y),p2,isAddPath,false);  
                }  
            }  
  
            return false;  
        }  
  
        private bool CheckTwoCornerDown(Point p1,Point p2,bool isAddPath)  
        {  
            //下  
            //清空记录  
            this.EmptyPathRecord();  
            for(int y = p1.Y +1; y<this.map.GetLength(1); y++)  
            {  
                if(this.map[p1.X,y]!=0)  
                    return false;  
                //允许记录  
                if(isAddPath)  
                {  
                    this.PathRecord.Add(new Point(p1.X,y));  
                }  
  
                //不允许清空  
                if(this.CheckOneCorner(new Point(p1.X,y),p2,false,false))  
                {  
                    return this.CheckOneCorner(new Point(p1.X,y),p2,isAddPath,false);  
                }  
            }   
            return false;  
        }  
  
        private void CopyArrayListTo(ref ArrayList srcAl,ref ArrayList destAl)  
        {  
            destAl.Clear();  
            destAl.TrimToSize();  
  
            foreach(Point p in srcAl)  
            {  
                Point newPnt = new Point(p.X,p.Y);  
                destAl.Add(newPnt);  
            }  
        }  
  
        private bool CheckTwoCorner(Point p1,Point p2)  
        {  
  
            //取起始x  
            Point CrossStart;  
            Point CrossEnd;  
  
            if(p1.X<p2.X)  
            {  
                CrossStart = p1;  
                CrossEnd = p2;  
            }  
            else  
            {  
                CrossStart = p2;  
                CrossEnd = p1;  
            }  
  
            //这里为寻找最短路径的算法  
            //方法很简单，因为当前的起点方向不确定，可以选择重复尝试能成功的起点  
            //然后找到路径最少的  
  
            //测试4次，寻找最短的路径  
  
            ArrayList[] backFindPath = new ArrayList[4];  
            bool isFind =false;  
            int nextPathList=0;  
            while(nextPathList<4)  
            {  
                backFindPath[nextPathList] = null;   
 
        if(this.CheckTwoCornerUp(CrossStart,CrossEnd,false))  
                {  
                    this.PathRecord.Clear();  
 
            this.CheckTwoCornerUp(CrossStart,CrossEnd,true);  
                    backFindPath[nextPathList] = new ArrayList();  
                    CopyArrayListTo(ref this.PathRecord,ref  
 
            backFindPath[nextPathList]);  
                    isFind = true;  
                    nextPathList ++;  
                }   
 
        if(this.CheckTwoCornerDown(CrossStart,CrossEnd,false))  
                {  
                    this.PathRecord.Clear();  
                    this.CheckTwoCornerDown(CrossStart,CrossEnd,true);  
                    backFindPath[nextPathList] = new ArrayList();  
                    CopyArrayListTo(ref this.PathRecord,ref backFindPath[nextPathList]);  
                    isFind = true;  
                    nextPathList ++;  
                }  
  
                if(this.CheckTwoCornerLeft(CrossStart,CrossEnd,false))  
                {  
                    this.PathRecord.Clear();  
                    this.CheckTwoCornerLeft(CrossStart,CrossEnd,true);  
                    backFindPath[nextPathList] = new ArrayList();  
                    CopyArrayListTo(ref this.PathRecord,ref backFindPath[nextPathList]);  
                    isFind = true;  
                    nextPathList ++;  
                }  
  
                if(this.CheckTwoCornerRight(CrossStart,CrossEnd,false))  
                {  
                    this.PathRecord.Clear();  
                    this.CheckTwoCornerRight(CrossStart,CrossEnd,true);  
                    backFindPath[nextPathList] = new ArrayList();  
                    CopyArrayListTo(ref this.PathRecord,ref backFindPath[nextPathList]);  
                    isFind = true;  
                    nextPathList ++;  
                }  
  
                //没有结果  
                if(!isFind)  
                    break;  
            }  
  
            //有结果返回  
            if(isFind)  
            {  
                //检查起点最小数  
                int minCount = 0;  
                //记录位  
                int index = 0;  
                for(int i=0;i<4;i++)  
                {  
                    if(backFindPath[i]!=null)  
                    {  
                        if(backFindPath[i].Count>0)  
                        {  
                            if(minCount==0)  
                            {  
                                minCount=backFindPath[i].Count;  
                                index = i;  
                            }  
                            else if(backFindPath[i].Count<minCount)  
                            {  
                                minCount = backFindPath[i].Count;  
                                index = i;  
                            }  
                        }  
                    }  
                }  
  
                //回复属性数据  
                this.PathRecord.Clear();  
                this.PathRecord.TrimToSize();  
                CopyArrayListTo(ref backFindPath[index],ref this.PathRecord);  
                  
                return true;  
            }  
  
            return false;  
        }  
  
  
        public bool Execute()  
        {  
            pathPointCount = -1;  
            //检查目标位置是否一样  
            if(this.startPos.X==this.endPos.X && this.startPos.Y==this.endPos.Y)  
            {  
                pathPointCount = -1;  
                return false;  
            }  
  
            //检查为同一横坐标  
            if(this.startPos.Y==this.endPos.Y)  
                if(this.CheckHorizontal(this.startPos,this.endPos))  
                {  
                    this.EmptyPathRecord();  
                    pathPointCount = 1;  
                    return (this.CheckHorizontal(this.startPos,this.endPos,true));  
                }  
  
            //检查为同一纵坐标  
            if(this.startPos.X==this.endPos.X)  
                if(this.CheckVertical(this.startPos,this.endPos))  
                {  
                    this.EmptyPathRecord();  
                    pathPointCount = 1;  
                    return (this.CheckVertical(this.startPos,this.endPos,true));  
                }  
  
            //检查一个折点  
            if(this.CheckOneCorner(this.startPos,this.endPos))  
            {  
                pathPointCount =2;  
                return true;  
            }  
  
            //检查两个折点  
            if(this.CheckTwoCorner(this.startPos,this.endPos))  
            {  
                pathPointCount =3;  
                return true;  
            }  
  
            return false;  
        }  
  
        /**//// <summary>  
        /// 起点坐标  
        /// </summary>  
        public Point StartPosition  
        {  
            get  
            {  
                return this.startPos;  
            }  
            set  
            {  
                this.startPos = value;  
            }  
        }  
  
        /**//// <summary>  
        /// 终点坐标  
        /// </summary>  
        public Point EndPosition  
        {  
            get  
            {  
                return this.endPos;  
            }  
            set  
            {  
                this.endPos = value;  
            }  
        }  
        /**//// <summary>  
        /// 地图数据  
        /// </summary>  
        public int[,] MapData  
        {  
            get  
            {  
                return this.map;  
            }  
            set  
            {  
                this.map = value;  
            }  
        }  
        /**//// <summary>  
        /// 获取折点数  
        /// </summary>  
        public int PathPointCount  
        {  
            get  
            {  
                return this.pathPointCount;  
            }  
        }  
  
        /**//// <summary>  
        /// 获取路径表  
        /// </summary>  
        public Point[] PathPointList  
        {  
            get  
            {  
                if(this.PathRecord.Count>=0)  
                {  
                    Point[] tmpPointList = new Point[this.PathRecord.Count];  
                    int i = 0;  
                    foreach(Point p in this.PathRecord)  
                    {  
                        tmpPointList[i] = p;  
                        i++;  
                    }  
                    return tmpPointList;  
                }  
                else  
                {  
                    return null;  
                }  
            }  
        }  
  
        public ArrayList PathPointArray  
        {  
            get  
            {  
                return this.PathRecord;  
            }  
        }  
  
    }  
}  

测试用例：

int[,] map = new int[14,10]  
                {  
                    {0,0,0,0,0,0,0,0,0,0},  
                    {0,2,0,3,1,0,0,0,0,0},  
                    {0,0,0,0,1,0,0,0,0,0},  
                    {0,1,1,1,1,1,1,1,1,0},  
                    {0,0,0,0,1,0,0,0,0,0},  
                    {0,0,0,0,1,0,0,0,0,0},  
                    {0,0,0,0,1,0,0,0,0,0},  
                    {0,0,0,0,1,0,0,0,0,0},  
                    {0,0,0,0,1,0,0,0,0,0},  
                    {0,0,0,0,1,0,0,0,0,0},  
                    {0,1,1,1,1,1,1,1,1,0},  
                    {0,0,0,0,1,0,0,0,0,0},  
                    {0,0,0,0,1,0,0,0,0,0},  
                    {0,0,0,0,0,0,0,0,0,0}  
                };  
    AI_Engine.TestPathing TP = new AI_Engine.TestPathing();  
    TP.StartPosition = new Point((int)numericUpDown1.Value,(int)numericUpDown2.Value);  
    TP.EndPosition = new Point((int)numericUpDown3.Value,(int)numericUpDown4.Value);  
    TP.MapData = this.map;  
 
    if(TP.Execute())  
    {  
        lbInfo.Text = "连通！";  
        AddPathInfo(TP.PathPointList);//绘制路径  
    }  
    else  
    {  
        lbInfo.Text = "不通！";  
    }  

Note:
map中0表示通道；1是障碍，2是起点，3是终点。

遍历map数组方法是

for(int y=0;y<10;y++)
for(int x=0;x<14;x++)
{
g.Draw ........ //绘制
}