poj 3009DFS回溯问题
题目大意就是给出一个w*h的地图，其中0代表空地，1代表障碍物，2代表起点，3代表终点，每次行动可以走多个方格，每次只能向附近一格不是障碍物的方向行动，直到碰到障碍物才停下来，此时障碍物也会随之消失,如果行动时超出方格的界限或行动次数超过了10则会game over .如果行动时经过3则会win，记下此时行动次数（不是行动的方格数），求最小的行动次数
由于题目相对较长，所以分的情况也比较多，注意不要漏掉了！
1.起点是没有障碍的，当做0的情况。
2.注意区分冰壶是运动的还是静止的，若是静止的话，旁边有障碍是不能走的。没有的话冰壶是停在障碍旁边而不是取代障碍，这是障碍消失，若是运动的话，它的运动方向是不能改变的。
3.注意坐标系的建立（我觉得两个坐标轴好像是反的，反正纠结了很久）。
4.还有什么只能移动十次，不能出界等等。考虑了这些，基本就能过了。
?
数据1： 3 2 可知起点的旁边是终点，故可以只需一步就到达终点
数据2：
1 0 0 2 1 0???????????????? 1 0 0 0 1 0????? 1 0 0 0 1 0????? 1 0 0 0 1 0???? 1 0 0 0 1 0
1 1 0 0 0 0???????????????? 1 1 0 0 0 0????? 1 1 0 0 0 0????? 1 0 0 0 0 0???? 1 0 0 0 0 0
0 0 0 0 0 3???????????????? 0 0 0 0 0 3????? 0 0 0 0 0 3????? 0 2 0 0 0 3???? 0 0 0 0 0 3/2
0 0 0 0 0 0???????????????? 0 0 0 0 0 0????? 0 0 0 0 0 0????? 0 0 0 0 0 0???? 0 0 0 0 0 0
1 0 0 0 0 1 可以这样移动??? 1 0 0 2 0 1 - >? 0 2 0 0 0 1? ->? 0 0 0 0 0 1 ->? 0 0 0 0 0 1
0 1 1 1 1 1???????????????? 0 1 1 0 1 1????? 0 1 1 0 1 1????? 0 1 1 0 1 1???? 0 1 1 0 1 1
故可以最小四步到达3
数据3:1 1 2 1 1 3 因为2的旁边都是障碍物，而能移动的条件是该方向附近一格无障碍物，所以2无路可走，故无法到达3，无解
其他数据的分析类似
由于题目给出要在10步内找到最优解，又每次可以向四个方向进行搜索，时间复杂度是O（4^10）=O((2^10)^2)=O(1000^2)=O(1000000)
在搜索时如果发现此时搜索的层次已经大于最优解，则可以回溯，因为继续向下搜也不会再出现更优解。
该开始的时候题目没看清，把输入长高高反了，WA了两次，最后终于发现了，下面是做题情况
不说了代码如下：
#include<iostream>#include<queue>using namespace std;struct point{int x,y;int step;};int flag[45][45];char map[45][45];int dir1[4][2]={{0,-1},{1,0},{0,1},{-1,0}};//zuo优先int dir2[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//you优先int d1,d2;int start[2];int end[2];int w,h;void init(){memset(flag,0,sizeof(flag));cin>>w>>h; for(int i=0;i<h;i++){cin>>map[i];for(int j=0;j<w;j++){if(map[i][j]=='#'){flag[i][j]=1;}if(map[i][j]=='S'){start[0]=i;start[1]=j;}if(map[i][j]=='E'){end[0]=i;end[1]=j;}}}if(start[0]==0){d1=1;d2=1;}else if(start[0]==h-1){d1=3;d2=3;}else if(start[1]==w-1){d1=2;d2=0;}else{ d1=0;d2=2;}}int dfs(int x,int y,int d,int dir[][2]){int step ,temp, tempx,tempy;if(x==end[0]&&y==end[1])return 1;for(int i=0;i<4;i++){temp=(d+i)%4;tempx=x+dir[temp][1];tempy=y+dir[temp][0];if(tempx>=0&&tempx<h&&tempy>=0&&tempy<w&&!flag[tempx][tempy])break;}step=dfs(tempx,tempy,(temp+3)%4,dir)+1;return step;}int bfs(){memset(flag,0,sizeof(flag));queue<point> q;point p;p.x=start[0];p.y=start[1];p.step=1;flag[p.x][p.y]=1;q.push(p);while(!q.empty()){p=q.front();q.pop();if(p.x==end[0]&&p.y==end[1])return p.step;for(int i=0;i<4;i++){point temp;temp.x=p.x+dir1[i][1];temp.y=p.y+dir1[i][0];if(temp.x>=0&&temp.x<h&&temp.y>=0&&temp.y<w&&map[temp.x][temp.y]!='#'&&!flag[temp.x][temp.y]){flag[temp.x][temp.y]=1;temp.step=p.step+1;q.push(temp);}}}return 0;}int main(){int T;cin>>T;while(T--){init();cout<<dfs(start[0],start[1],d1,dir1)<<" ";cout<<dfs(start[0],start[1],d2,dir2)<<" ";cout<<bfs()<<endl;}}?
?
?关于DFS一般都会与回溯相结合起来，这方面自己有一点理解，但是还不是那么懂，有待学习！！
?
?
?