题目链接: http://poj.org/problem?id=3009
//思路 直接搜索 只是和一般的不同 它会一直走下去 直到碰壁为止 但是这里用一个巧妙点的办法 也是一步一步地走 只是用参数来确定下方向 //总结: 注意在碰壁的时候 就可以进行对四面的搜索而不是单方向的搜索 但是要注意的是 step不要加一 //因为在 下次dfs的时候会加一 wa在这真可惜
这里用的搜索还是一步一步的走 只是用了一个参数temp 来告诉我们这步应该怎么走
要么是单方向的 走 要么可以向四周搜索 这个方法也是突发奇想想到了 不然一直走下去那样做要浪费很多代码
#include<iostream> #include<cstring> using namespace std; #define maxn 25 int map[maxn][maxn]; int vis[maxn][maxn]; int px[4]={0,-1,0,1}; int py[4]={-1,0,1,0}; int n,m,flag,ans; void dfs(int i,int j,int step,int temp) { if(i<1||i>n||j<1||j>m) return ; //注意 步数大于10 输出-1 if(step>10) return ; if(map[i][j]==3) { ans = min(ans,step); return ; } //优化一下 给当前的点设置一个状态 为0 则可以向四周搜 否则只能单方向移动 if(temp==0) { for(int k=0;k<4;k++) { int x = i+px[k]; int y = j+py[k]; if(map[x][y]!=1) dfs(x,y,step+1,k+1);//注意 只有在此处 为 step+1 } } else if(temp==1)//对应上面的k==0 那么只能向左走 { int x = i; int y = j-1; if(map[x][y]!=1)//可以走 dfs(x,y,step,temp);//继续左 else if(map[x][y]==1)//不能走 { map[x][y] = 0;//碰点置空 y++;//回退到上一步 dfs(x,y,step,0);//向四周搜 y--; map[x][y] = 1; } } else if(temp==2)//向上走 { int x = i-1; int y = j; if(map[x][y]!=1)//可以走 dfs(x,y,step,temp);//继续上 else if(map[x][y]==1)//不能走 { map[x][y] = 0;//碰点置空 x++;//回退到上一步 dfs(x,y,step,0);//向四周搜 x--; map[x][y] = 1; } } else if(temp==3)//向右 { int x = i; int y = j+1; if(map[x][y]!=1)//可以走 dfs(x,y,step,temp);//继续左 else if(map[x][y]==1)//不能走 { map[x][y] = 0;//碰点置空 y--;//回退到上一步 dfs(x,y,step,0);//向四周搜 y++; map[x][y] = 1; } } else if(temp==4)//向下 { int x = i+1; int y = j; if(map[x][y]!=1)//可以走 dfs(x,y,step,temp);//继续下 else if(map[x][y]==1)//不能走 { map[x][y] = 0;//碰点置空 x--;//回退到上一步 dfs(x,y,step,0);//向四周搜 x++; map[x][y] = 1; } } } int main() { while(scanf("%d%d",&m,&n)!=EOF) { if(m==0&&n==0) break; int bi,bj; memset(map,0,sizeof(map)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&map[i][j]); if(map[i][j]==2) { bi=i; bj=j; } } memset(vis,0,sizeof(vis)); flag = 0; ans = 1e9; dfs(bi,bj,0,0); if(ans==1e9) printf("-1\n"); else printf("%d\n",ans); } return 0; }