最少步数

时间限制：

3000 ms  |  内存限制：

65535 KB

难度：

4

 

描述

这有一个迷宫，有0~8行和0~8列：

 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表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

 

输入

第一行输入一个整数n（0<n<=100），表示有n组测试数据;

随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。

输出

输出最少走几步。

样例输入

23 1  5 73 1  6 7

样例输出

1211

1 #include
         
           2 #include
          
            3 using namespace std; 4  5 struct point 6 { 7     int x,y,step; 8 }; 9 int dir[4][2]={-1,0,0,1,1,0,0,-1};10 11 int BFS(point s,point t,int map[9][9])12 {13     queue
           
             q;14     int i;15     point tmp;16     q.push(s);17     while(1)18     {19         if(s.x==t.x&&s.y==t.y)20             return s.step;21         for(i=0;i<4;++i)22         {23             tmp.x=s.x+dir[i][0];24             tmp.y=s.y+dir[i][1];25             if(map[tmp.x][tmp.y]==0)26             {27                 tmp.step=s.step+1;28                 map[tmp.x][tmp.y]=1;29                 q.push(tmp);30             }31         }32         s=q.front();33         q.pop();34     }35 }36 37 int main()38 {39     int T;40     point s,t;41     scanf("%d",&T);42     while(T--)43     {44         int map[9][9]={
       1,1,1,1,1,1,1,1,1,45                        1,0,0,1,0,0,1,0,1,46                        1,0,0,1,1,0,0,0,1,47                        1,0,1,0,1,1,0,1,1,48                        1,0,0,0,0,1,0,0,1,49                        1,1,0,1,0,1,0,0,1,50                        1,1,0,1,0,1,0,0,1,51                        1,1,0,1,0,0,0,0,1,52                        1,1,1,1,1,1,1,1,1,};53         scanf("%d%d%d%d",&s.x,&s.y,&t.x,&t.y);54         s.step=0;55         map[s.x][s.y]=1;56         printf("%d\n",BFS(s,t,map));57     }58     return 0;59 }