题意：大模拟DFS就是模拟摸摸摸
分析：结合代码给出，见下方代码
收获：对于萌新来说每一次都有新收获。
写DFS还是要从整体的角度看问题，比如这个题中的障碍的撞碎问题怎么模拟，可以利用每次深搜到尽头之后修复被撞碎的障碍来保证其他的DFS正确（看的学长的思路，这一手很皮的）。
对于一直前进的处理就是for()来确定方向，不停向前for（int j=0; ;j++)利用j来求出x和y的实时坐标。
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; int m,n; int s[50][50]; int bx,by,ex,ey; int steep; int dx[]= {1,0,-1,0};//前进的方向 int dy[]= {0,1,0,-1};//前进的方向 int min_steep=1500000; bool not_in(int x1,int y1)//判断是否越界 { if(x1<0||x1>=m||y1<0||y1>=n) return true; return false; } void DFS(int x,int y,int cur) { if(cur>10) return ;//超过十步就结束搜索。 if(cur>=min_steep) return ;//如果继续搜索下去一定找不到比现在更短的路径的时候就结束搜索 if(s[x][y]==3)//到达终点 { min_steep=min(cur,min_steep); return ; } for(int i=0; i<4; i++) { for(int j=1;; j++)//一直往前 { int nx=x+j*dx[i]; int ny=y+j*dy[i];//当前点的坐标 if(not_in(nx,ny)) { break; } if(j==1&&s[nx][ny]==1) break;//被卡住了就结束 if(s[nx][ny]==3) { DFS(nx,ny,cur+1); return; } if(s[nx][ny]==1) { int lx=nx-dx[i]; int ly=ny-dy[i]; s[nx][ny]=0; DFS(lx,ly,cur+1); s[nx][ny]=1;//这里很巧妙，在每次深度搜索到尽头之后会再修复破坏的障碍，让下次的深搜再使用，双击666 break; } } } } int main () { while(cin >> n >> m) { min_steep=150000; for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { scanf("%d",&s[i][j]); if(s[i][j]==2) { bx=i; by=j; } if(s[i][j]==3) { ex=i; ey=j; } } } // cout << bx << " " << by << endl; // cout << ex << " " << ey << endl; DFS(bx,by,0); if( min_steep ==150000) cout << "-1" << endl; else cout << min_steep <<endl; } return 0; }
