问题标题: 酷町堂：1257 迷宫寻宝

1257   迷宫寻宝

经验值：1600 时间限制：3000毫秒

题目描述 Description

小王设计了一个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

0表示道路，1表示墙。

现在输入一个坐标作为起点，再输入一个坐标作为宝贝的存放位置，问现在由你从起点出发，最少经过多少步可以寻到宝贝

输入描述 Input Description

第一行输入一个整数n（0<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，宝贝的行、列。

输出描述 Output Description

输出n行，每行输出最少走几步，如果找不到宝贝，输出0。
（如果输入的起点、终点是墙的位置，则也拿不到宝贝，输出0）

样例输入 Sample Input

2 3 1 5 7 3 1 6 7

样例输出 Sample Output

12 11

数据范围及提示 Data Size & Hint

每次只能往上、下、左、右相邻的格子走1步，且不能超出迷宫边界。

#include<iostream>
#include<cstring>
using namespace std;
int n,a,b,c,d,ans=100000000,dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool vis[105][105];
bool map[105][105]={
    {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},
};
void dfs(int x,int y,int bs){
    if(x==c&&y==d){
        ans=min(ans,bs);
        return;
    }
    for(int i=0;i<4;i++){
        int ax=dir[i][0]+x,ay=dir[i][1]+y;
        if(ax>=0&&ax<=8&&ay>=0&&ay<=8&&map[ax][ay]==0&&vis[ax][ay]==false){
            vis[ax][ay]=true;
            dfs(ax,ay,bs+1);
            vis[ax][ay]=false;
        }
    }
}
int main(){
    cin>>n;
    while(n--){
        cin>>a>>b>>c>>d;
        vis[a][b]=true;
        if(map[a][b]==1||map[c][d]==1){
            cout<<"0"<<endl; 
        }
        dfs(a,b,0);
        cout<<ans<<endl;
        ans=1000000;
    }
    return 0;
}