NYOJ 58 最少步数(dfs或者bfs)

       这道题最开始是用dfs做的，后来学会了bfs以后有一次用bfs做了这道题，但是奇迹般的TLE了，当时还纠结了半天最少步数竟然不能用bfs做吗？然后刚刚又用bfs交了一次，又奇迹般的AC了，这道题可以当作bfs的模板了。下面把bfs和dfs的代码都贴上吧。

AC代码（DFS）：

#include <iostream>
#include <cstring>
using namespace std;
int MAP[9][9] = { 1,1,1,1,1,1,1,1,1,          //定义地图
                  1,0,0,1,0,0,1,0,1,
                  1,0,0,1,1,0,0,0,1,
                  1,0,1,0,1,1,0,1,1,
                  1,0,0,0,0,1,0,0,1,
                  1,1,0,1,0,1,0,0,1,
                  1,1,0,1,0,1,0,0,1,
                  1,1,0,1,0,0,0,0,1,
                  1,1,1,1,1,1,1,1,1};
int dir[4][2] =  {1,0,0,1,-1,0,0,-1};          // 控制走的四个方向
int vis[9][9];                                 // 标记数组
int n,step,INF;
int S_x,S_y,E_x,E_y;

void dfs(int x,int y,int step){
  if(E_x==x &&E_y == y){              // 达到终点后取最小的那个值
    if(INF>step)
    INF=step;
    return ;
  }
  for(int i=0;i<4;i++){
    int X = x + dir[i][0];
    int Y = y + dir[i][1];
    if(X>=0&&Y>=0&&X<9&&Y<9&&MAP[X][Y]==0&&vis[X][Y]==0){
      vis[X][Y] = 1;
      dfs(X,Y,step+1);
      vis[X][Y] = 0;           // 出来时要取消标记
    }
  }
}
int main()
{
  cin>>n;
  while(n--){
    step = 0;               // 将步数初始化为0
    INF = 0x3f3f3f3f;       // 因为要求最少步数，所以将INF初始化为最大值
    memset(vis,0,sizeof(vis));
    cin>>S_x>>S_y>>E_x>>E_y;
    dfs(S_x,S_y,step);
    cout<<INF<<endl;
  }
  return 0;
}
/***
   [来源] NYOJ 58
   [题目] 最少步数
   [大意]
      就是一道入门的搜索题，也算是模板题了。详细看代码注释吧。
   [输入]
       2
       3 1 5 7
       3 1 6 7
    [输出]
       12
       11
*/

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
int MAP[9][9] = { 1,1,1,1,1,1,1,1,1,          //定义地图
                  1,0,0,1,0,0,1,0,1,
                  1,0,0,1,1,0,0,0,1,
                  1,0,1,0,1,1,0,1,1,
                  1,0,0,0,0,1,0,0,1,
                  1,1,0,1,0,1,0,0,1,
                  1,1,0,1,0,1,0,0,1,
                  1,1,0,1,0,0,0,0,1,
                  1,1,1,1,1,1,1,1,1};
int dir[4][2] =  {1,0,0,1,-1,0,0,-1};          // 控制走的四个方向
int vis[9][9];                                 // 标记数组
int n;
struct Node{
  int x,y,step;
}Now,Next,S,E;

int bfs(){                                // 广搜
  memset(vis,0,sizeof(vis));              // 清空标记数组
  queue<Node> q;                          // 定义队列
  S.step = 0;
  q.push(S);            // 入队
  while(!q.empty()){    // 如果队列不是空的就循环
    Now = q.front();    // 读取队首元素
    q.pop();            // 把队首弹出
    if(Now.x == E.x && Now.y == E.y){         // 当走到终点返回步数
      return Now.step;
    }
    for(int i=0;i<4;i++){
      Next.x = Now.x + dir[i][0];
      Next.y = Now.y + dir[i][1];
      if(Next.x >=0 && Next.y >=0 && Next.x < 9 && Next.y < 9 && MAP[Next.x][Next.y]==0 && vis[Next.x][Next.y]==0){
        vis[Next.x][Next.y] = 1;
        Next.step = Now.step + 1;
        q.push(Next);
      }
    }
  }
  return -1;
}

int main()
{
  scanf("%d",&n);
  while(n--){
    cin>>S.x>>S.y>>E.x>>E.y;
    int temp = bfs();
    printf("%d\n",temp);
  }
  return 0;
}