找朋友

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

X，作为户外运动的忠实爱好者，总是不想呆在家里。现在，他想把死宅Y从家里拉出来。问从X的家到Y的家的最短时间是多少。

为了简化问题，我们把地图抽象为n*n的矩阵，行编号从上到下为1 到 n，列编号从左到右为1 到 n。矩阵中’X’表示X所在的初始坐标，’Y’表示Y的位置 , ’#’表示当前位置不能走，’ * ’表示当前位置可以通行。X每次只能向上下左右的相邻的 ’*’ 移动，每移动一次耗时1秒。

输入

多组输入。每组测试数据首先输入两个整数n，m(1<= n ,m<=15 )表示地图大小。接下来的n 行，每行n个字符。保证输入数据合法。

输出

若X可以到达Y的家，输出最少时间，否则输出 -1。

示例输入

3 3X#Y***#*#3 3X#Y*#*#*#

示例输出

4-1

方法一：

BFS

#include 
     
      #include 
      
       #include 
       
        int n,m;struct node{    int x,y,ans;}q[250];char ma[16][16];//存放图的数组int vis[16][16];//标记访问过的点int mv[4][2]={
   {1,0},{0,1},{-1,0},{0,-1}};//控制方向的数组void BFS(int x,int y){    struct node j,h;    j.x=x;    j.y=y;    j.ans=0;    int jin=0,chu=0;    q[jin++]=j;//让j进栈    vis[j.x][j.y]=1;//当前访问的点标记为1    while(chu
        
         =0&&j.x
         
          =0&&j.y
         
        
       
      
     

方法二：

DFS

#include 
     
      #include 
      
       #include 
       
        const int INF = 1<<20;//定义一个大数struct node{    int x,y,ans;};char ma[16][16];int vis[16][16];int n,m,mi;int mv[4][2]={
   {0,1},{1,0},{-1,0},{0,-1}};void DFS(int x,int y,int ans){    if(ans>=mi)    {        return;    }//结束递归调用，防止超时    if(ma[x][y]=='Y')    {        if(ans
        
         =0&&f.y
         
          =0&&f.x