走迷宫（同一）：最短路径

//走迷宫（一）
//前提：迷宫图已知。给你一个起点和终点
//问题：至少几步到达终点
//问题隐含条件：1、肯定走得到终点；2,、求最短路径的问题（可以用队列+BFS）


#include<iostream>
using namespace std;

#define min(a,b) a<b?a:b

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 a, b, c, d, num;

int dfs(int x, int y, int dep)   //dep代表当前DFS的深度
{
    if (Map[x][y])   //if(走不下去了)
    {
        return 1;
    }
    if (x == c&&y == d)  //if(找到解了)
    {
        num = min(dep, num);
        return 0;
    }

    //枚举下一种情况，DFS(...,dep+1)
    Map[x][y] = 1;
    dfs(x - 1, y, dep+1);
    dfs(x + 1, y, dep + 1);
    dfs(x, y - 1, dep + 1);
    dfs(x, y + 1, dep + 1);
    Map[x][y] = 0;

}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        num = 10000;
        cin >> a >> b>>c>>d;
        dfs(a,b,0);
        cout << num << endl;
    }
}