nyoj--58--最少步数(bfs&dfs)

柔光的暖阳◎ 2022-06-11 06:45 178阅读 0赞

## 最少步数 ##

时间限制： 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）分别表示起点的行、列，终点的行、列。

输出

输出最少走几步。

样例输入

2
    3 1  5 7
    3 1  6 7

样例输出

12
    11

dfs:

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 int&nbsp;dx[ 
 4]&nbsp;=&nbsp;{&nbsp;- 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0}; 
 
 int&nbsp;dy[ 
 4]&nbsp;=&nbsp;{ 
 0,&nbsp; 
 0,&nbsp;- 
 1,&nbsp; 
 1}; 
 
 int&nbsp;c,&nbsp;step,&nbsp;ex,&nbsp;ey; 
 
 int&nbsp;Map[ 
 9][ 
 9]&nbsp;=&nbsp;{&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}; 
 
 void&nbsp;dfs( 
 int&nbsp;x,&nbsp; 
 int&nbsp;y,&nbsp; 
 int&nbsp;c) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(x&nbsp;==&nbsp;ex&nbsp;&amp;&amp;&nbsp;y&nbsp;==&nbsp;ey) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(c&nbsp;&lt;&nbsp;step) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;step&nbsp;=&nbsp;c; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp; 
 4;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;xx&nbsp;=&nbsp;x&nbsp;+&nbsp;dx[i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;yy&nbsp;=&nbsp;y&nbsp;+&nbsp;dy[i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(Map[xx][yy]&nbsp;==&nbsp; 
 0&nbsp;&amp;&amp;&nbsp;c&nbsp;&lt;&nbsp;step&nbsp;-&nbsp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map[xx][yy]&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dfs(xx,&nbsp;yy,&nbsp;c&nbsp;+&nbsp; 
 1); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map[xx][yy]&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;t; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;t); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(t--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;x,&nbsp;y; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;step&nbsp;=&nbsp; 
 9999; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d&nbsp;%d&nbsp;%d&nbsp;%d",&nbsp;&amp;x,&nbsp;&amp;y,&nbsp;&amp;ex,&nbsp;&amp;ey); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map[x][y]&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dfs(x,&nbsp;y,&nbsp;c); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map[x][y]&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n",&nbsp;step); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

bfs:

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 int&nbsp;dx[ 
 4]&nbsp;=&nbsp;{&nbsp;- 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0}; 
 
 int&nbsp;dy[ 
 4]&nbsp;=&nbsp;{ 
 0,&nbsp; 
 0,&nbsp;- 
 1,&nbsp; 
 1}; 
 
 int&nbsp;c,&nbsp;step,&nbsp;ex,&nbsp;ey; 
 
 int&nbsp;x,&nbsp;y; 
 
 int&nbsp;vis[ 
 9][ 
 9]; 
 
 int&nbsp;Map[ 
 9][ 
 9]&nbsp;=&nbsp;{&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 1,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 0,&nbsp; 
 1, 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1,&nbsp; 
 1 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}; 
 
 struct&nbsp;node 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;x,&nbsp;y,&nbsp;step; 
 }; 
 
 
 int&nbsp;bfs() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;queue&nbsp;&lt;node&nbsp;&gt;qu; 
 
 &nbsp;&nbsp;&nbsp;&nbsp;node&nbsp;s,&nbsp;now,&nbsp;next;&nbsp; 
 ///s为第一个访问的节点 &nbsp;&nbsp;&nbsp;&nbsp;s.x&nbsp;=&nbsp;x; 
 &nbsp;&nbsp;&nbsp;&nbsp;s.y&nbsp;=&nbsp;y; 
 &nbsp;&nbsp;&nbsp;&nbsp;s.step&nbsp;=&nbsp; 
 0; 
 
 &nbsp;&nbsp;&nbsp;&nbsp;vis[x][y]&nbsp;=&nbsp; 
 1;&nbsp; 
 ///对访问过的点进行标记 
 &nbsp;&nbsp;&nbsp;&nbsp;qu.push(s); 
 ///第一个点入队 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(!qu.empty()) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;now&nbsp;=&nbsp;qu.front();&nbsp; 
 ///把正在访问的点提出来 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qu.pop();&nbsp;&nbsp; 
 ///提出来后进行出队操作，把他相邻符合条件的点全部入队 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///找到终点 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(now.x&nbsp;==&nbsp;ex&nbsp;&amp;&amp;&nbsp;now.y&nbsp;==&nbsp;ey) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;now.step; 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 0;&nbsp;i&nbsp;&lt;&nbsp; 
 4;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next.x&nbsp;=&nbsp;now.x&nbsp;+&nbsp;dx[i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next.y&nbsp;=&nbsp;now.y&nbsp;+&nbsp;dy[i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next.step&nbsp;=&nbsp;now.step; 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(Map[next.x][next.y]&nbsp;==&nbsp; 
 0&nbsp;&amp;&amp;&nbsp;vis[next.x][next.y]&nbsp;==&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;vis[next.x][next.y]&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next.step&nbsp;+=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qu.push(next); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;t; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;t); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(t--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(vis,&nbsp; 
 0,&nbsp; 
 sizeof(vis)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d&nbsp;%d&nbsp;%d&nbsp;%d",&nbsp;&amp;x,&nbsp;&amp;y,&nbsp;&amp;ex,&nbsp;&amp;ey); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n",&nbsp;bfs()); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>