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一般都会与回溯相结合起来，这方面自己有一点理解，但是还不是那么懂，有待学习！！