题解 | #迷宫问题#

//哈哈我这个自学的没看什么广度优先搜索就靠学过的回溯也做出这道题了，成就感满满 //思路就是记录路径，加入list，判断有没有路可以走，如果可走的路已经存在于list中那么就回溯 直到最后返回。代码比较乱先这样吧，明天再修改看看

using System; using System.Linq; using System.Collections.Generic;

class Program {

static int x, y;

static List<int[]> list;
static void Main(string[] args)
{
 string num=(Console.ReadLine());
    string[] ss=num.Split(' ');
    int[,] mi = new int[int.Parse(ss[0]), int.Parse(ss[1])];
    int[,] mi2 = new int[int.Parse(ss[0]+2), int.Parse(ss[1]+2)];
    int[,] temp = new int[int.Parse(ss[0] + 2), int.Parse(ss[1] + 2)];
    list = new List<int[]>();
  
    x= int.Parse(ss[0]);
    y= int.Parse(ss[1]);
    for (int i = 0; i < int.Parse(ss[0]) + 2; i++)
    {
        for (int j = 0; j < int.Parse(ss[1]) + 2; j++)
        {
            mi2[i, j] = 1;
            temp[i, j] = 1;
        }

    }

    for (int i = 0; i < int.Parse(ss[0]); i++)
    {
        string num1 = (Console.ReadLine());
        string[] sss = num1.Split(' ');
        for (int j= 0; j < int.Parse(ss[1]); j++)
        {
            mi[i, j] = int.Parse(sss[j]);
           // Console.Write(mi[i, j]+" ");
        }
      //  Console.WriteLine();
    }
    for (int i = 1; i < int.Parse(ss[0])+1; i++)
    {
        for (int j = 1; j < int.Parse(ss[1])+1; j++)
        {
            mi2[i, j] = mi[i-1,j-1];
            temp[i, j] = temp[i - 1, j - 1];
        }

    }
    //for (int i = 0; i < int.Parse(ss[0]) + 2; i++)
    //{
    //    for (int j = 0; j < int.Parse(ss[1]) + 2; j++)
    //    {
    //        Console.Write(mi2[i, j]+" ");
    //    }
    //   Console.WriteLine();
    //}
   
    migong(1,1,x,y, mi2);
}
public static void migong(int i,int j,int k,int l,int [,] vs)
{

    if (i == k && j == l)
    {
       // Console.WriteLine("find");
        Console.WriteLine("(0,0)");
        for (int n = 0; n < list.Count; n++)
        {
            Console.WriteLine("("+ (list[n][0]-1)+ ","+(list[n][1]-1)+")");

        }


    }
    else {
      
      int [] vs1= new int[2] { i + 1, j };
        int[] vs2 = new int[2] { i - 1, j };
        int[] vs3 = new int[2] { i , j + 1 };
        int[] vs4 = new int[2] { i, j -1 };
        if (vs[i+1,j]==0&&!contain(list,vs1)) {
            list.Add(new int[2] {i+1,j });
           
            migong(i + 1, j,k,l, vs); 

            list.RemoveAt(list.Count-1);
        }
        if (vs[i -1, j] == 0 && !contain(list, vs2))
        {
            list.Add(new int[2] { i- 1, j });
            migong(i - 1, j, k, l, vs);

            list.RemoveAt(list.Count - 1);
        }
        if (vs[i, j + 1] == 0 && !contain(list, vs3))
        {
            list.Add(new int[2] { i , j + 1 });
            migong(i, j + 1, k, l, vs);

            list.RemoveAt(list.Count - 1);
        }
        if (vs[i , j-1] == 0 && !contain(list, vs4))
        {
            list.Add(new int[2] { i , j - 1 });
            migong(i, j - 1, k, l, vs);

            list.RemoveAt(list.Count - 1);
        }
     
      
       
    }


}
public static bool contain(List<int []> vs,int [] vs1) {
    for (int i = 0; i < vs.Count; i++)
    {
            if (vs[i][0] == vs1[0]&& vs[i][1] == vs1[1]) {
            return true;
        }
        
    }
    return false;
}

}