最少步數

時間限制：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

1 2 #include <stdio.h> 3 int tu[9][9]={ 4 1,1,1,1,1,1,1,1,1, 5 1,0,0,1,0,0,1,0,1, 6 1,0,0,1,1,0,0,0,1, 7 1,0,1,0,1,1,0,1,1, 8 1,0,0,0,0,1,0,0,1, 9 1,1,0,1,0,1,0,0,1, 10 1,1,0,1,0,1,0,0,1, 11 1,1,0,1,0,0,0,0,1, 12 1,1,1,1,1,1,1,1,1, 13 }; 14 int bs[9][9]={0}; 15 int min=32; 16 17 int DFS(int a,int b,int c,int d,int count)/*起始位置（a,b），終點位置（c,d）,步數count 初值為 0 */ 18 { 19 if(tu[a][b]==1) return count; 20 else 21 { 22 if(a==c&&b==d) 23 { 24 if(min>count) min=count; 25 } 26 bs[a][b]=1; 27 28 if((!tu[a-1][b])&&(!bs[a-1][b]))/*上邊*/ 29 count=DFS(a-1,b,c,d,count+1); 30 if((!tu[a+1][b])&&(!bs[a+1][b]))/*下邊*/ 31 count=DFS(a+1,b,c,d,count+1); 32 if((!tu[a][b-1])&&(!bs[a][b-1]))/*左邊*/ 33 count=DFS(a,b-1,c,d,count+1); 34 if((!tu[a][b+1])&&(!bs[a][b+1]))/*右邊*/ 35 count=DFS(a,b+1,c,d,count+1); 36 37 bs[a][b]=0; 38 39 return count-1; 40 } 41 } 42 43 int main(void) 44 { 45 int a,b,c,d,n,count; 46 scanf("%d",&n); 47 while(n--) 48 { 49 count=0; 50 min=30; 51 scanf("%d%d%d%d",&a,&b,&c,&d); 52 if(tu[a][b]==0 && tu[c][d]==0) 53 { 54 DFS(a,b,c,d,count); 55 printf("%d\n",min); 56 } 57 } 58 return 0; 59 } 60

?

轉載于:https://www.cnblogs.com/xiaoyunoo/p/3516875.html

總結

以上是生活随笔為你收集整理的最少步数----深搜的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。