本文主要是介绍poj 3083 深搜+广搜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
如题：http://poj.org/problem?id=3083
今天可是元旦，好想找妹纸出去玩啊...算了 还是敲代码吧............~~~~
题目给出一个迷宫，'#'是墙，不能走，‘.’是路，能走，要从起点‘S’走到终点'E'。
题目要分别输出3中走法的步数，第一种左转优先，第二种右转优先。注意，如果是第一种，当前这一步是右转得来的，下一步按照规则岂不是又左转走回去了？
所以要对方向数组进行处理。这一步是右转的时候，下一步要首先判断上，下，右能不能走，如果不能走，才左转。右转优先也同理。开顺时针方向数组左下右上和逆时针方向数组右上左下。通过下一步方向=（当前方向+j（0~3）+3）%4进行判断，具体看代码。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 42
char path[N][N];
int T,w,h;
int c,c1,c2;
int dir[][2]={0,-1,-1,0,0,1,1,0};
int dir1[][2]={0,1,-1,0,0,-1,1,0};
int xs,ys,xe,ye;
int vis[N][N];
struct node
{
int x,y,dist;
};
int DFS(int x,int y,int I,int di[][2])//di[][0、1]区别向左还是向右
{
if(x==xe&&y==ye)
return 1;
int i,j;
for(j=0;j<4;j++)
{
i=(I+j+3)%4;
int tx=x+di[i][0];
int ty=y+di[i][1];
if(tx>=0&&ty>=0&&tx<h&&ty<w&&path[tx][ty]!='#')
{
c=DFS(tx,ty,i,di)+1;
break;
}
}
return c;
}
int bfs(int x,int y)
{
queue<node>q;
node u;
u.x=x;u.y=y;u.dist=1;
vis[u.x][u.y]=1;
q.push(u);
while(!q.empty())
{
u=q.front();
int d=u.dist+1;
if(u.x==xe&&u.y==ye)
return u.dist;
q.pop();
int i;
for(i=0;i<4;i++)
{
node v;
v.x=u.x+dir[i][0];
v.y=u.y+dir[i][1];
if(v.x>=0&&v.y>=0&&v.x<h&&v.y<w&&!vis[v.x][v.y]&&path[v.x][v.y]!='#')
{
vis[v.x][v.y]=1;
v.dist=d;
q.push(v);
}
}
}
return 0;
}
int main()
{
freopen("C:\\1.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
c1=c2=0;
int i,j;
scanf("%d%d",&w,&h);
getchar();
for(i=0;i<h;i++)
scanf("%s",path[i]);
for(i=0;i<h;i++)
for(j=0;j<w;j++)
{
if(path[i][j]=='S')
{
xs=i;
ys=j;
}
if(path[i][j]=='E')
{
xe=i;
ye=j;
}
}
memset(vis,0,sizeof(vis));
int starti;
for(i=0;i<4;i++)
{
int tx=xs+dir[i][0];
int ty=ys+dir[i][1];
if(tx>=0&&ty>=0&&tx<h&&ty<w&&path[tx][ty]!='#')
{
starti=i;
break;
}
}
c1=DFS(xs,ys,starti,dir);
for(i=0;i<4;i++)
{
int tx=xs+dir1[i][0];
int ty=ys+dir1[i][1];
if(tx>=0&&ty>=0&&tx<h&&ty<w&&path[tx][ty]!='#')
{
starti=i;
break;
}
}
c2=DFS(xs,ys,starti,dir1);
c=bfs(xs,ys);
printf("%d %d %d\n",c1,c2,c);
}
return 0;
}
这篇关于poj 3083 深搜+广搜的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
