PS：以前看到題目這么長就沒寫下去了。今天做了半天，沒做出來。準(zhǔn)備看題解，打開了網(wǎng)站都忍住了，最后還是靠自己做出來的。算是一點(diǎn)進(jìn)步吧。

分析：

　　題目的意思沒明白或者理解有偏差都沒辦法做題。看樣例3和樣例4，數(shù)據(jù)差不多的，但是一個輸出4，但是另外的一個卻是-1。再去看題目就會發(fā)現(xiàn)，題目的意思是在撞碎石頭之前必須走一個為值0的格子。我理解為需要加速。對樣例4，答案4是這樣出來的：初始位置為（1，3），第一步是到達(dá)（1，2），并且使得（1，1）點(diǎn)的值為0（撞碎了這里的石頭，0代表可以通行）；第二步是到達(dá)（1，3），并且是得（1，4）點(diǎn)的值為0；第三步是到達(dá)（1，4），并且使得（1，5）的值為0；第四步是到達(dá)（1，5），發(fā)現(xiàn)到達(dá)了終點(diǎn)，結(jié)束。樣例5也可以這樣得到。

　　樣例6錯誤的原因是因為超過了10步，這是題目的要求，超過10步就當(dāng)不能到達(dá)處理。

　　這樣一來，可以知道了起點(diǎn)和終點(diǎn)的處理了。起點(diǎn)（終點(diǎn)）的坐標(biāo)記錄下來，但是標(biāo)記為0。

　　還有就是實(shí)現(xiàn)如何對一個方向進(jìn)行搜索，以及如何標(biāo)記在撞石頭之前已經(jīng)走過0的位置（不能是這種情況：起點(diǎn)是0，下一點(diǎn)就撞石頭）。這思考一下就可以實(shí)現(xiàn)了。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 void DFS(int x,int y,int di); 8 const int N=22,INF=0x3f3f3f3f; 9 bool vis[N][N]; 10 int r,c,t,ex,ey,sx,sy,mx; 11 int dx[4]={0,0,1,-1}; 12 int dy[4]={1,-1,0,0}; 13 bool isin(int x,int y) 14 { 15 return x>=0&&x<r&&y>=0&&y<c; 16 } 17 void DDFS(int a,int b,int x,int y,int d) 18 { 19 int i,j; 20 if(t>10) return ; 21 i=x+a; j=y+b; 22 if(!isin(i,j)) return ; 23 if(!vis[i][j]) 24 { 25 d=1; 26 if(i==ex&&j==ey) 27 { 28 mx=min(t,mx); 29 } 30 DDFS(a,b,i,j,d); 31 } 32 else if(vis[i][j]&&d) 33 { 34 vis[i][j]=0; 35 d=0; 36 t++; 37 DFS(x,y,d); 38 t--; 39 vis[i][j]=1; 40 } 41 } 42 void DFS(int x,int y,int d) 43 { 44 45 for(int k=0;k<4;k++) 46 { 47 DDFS(dx[k],dy[k],x,y,d); 48 } 49 } 50 int main() 51 { 52 //freopen("test.txt","r",stdin); 53 while(scanf("%d%d",&c,&r)!=EOF&&c) 54 { 55 int x; 56 for(int i=0;i<r;i++){ 57 for(int j=0;j<c;j++){ 58 scanf("%d",&x); 59 if(x==3) 60 { 61 ex=i;ey=j; 62 vis[i][j]=0; 63 } 64 else if(x==2) 65 { 66 sx=i;sy=j; 67 vis[i][j]=0; 68 } 69 else vis[i][j]=x; 70 } 71 } 72 t=1; 73 mx=INF; 74 DFS(sx,sy,0); 75 if(mx==INF) printf("-1\n"); 76 else printf("%d\n",mx); 77 } 78 return 0; 79 } View Code

　　DFS(x,y,d) ： (x,y)是起點(diǎn)的坐標(biāo)，d是標(biāo)記是否有經(jīng)過被標(biāo)記0的點(diǎn)。1表示經(jīng)過了，0表示沒有。

　　DDFS(a,b,x,y,d) ：(a,b)是方向向量，表明向什么方向搜索；x,y,d同上。

　　通過d的記錄就可以知道石頭可不可以撞碎。使用(a,b)就可以沿著同一方向一直深入。

?

轉(zhuǎn)載于:https://www.cnblogs.com/Potato-lover/p/4114002.html

總結(jié)

以上是生活随笔為你收集整理的poj3009 Curling 2.0 深搜的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。