poj 3083 深搜+广搜

2024-04-28 17:38

文章标签 poj 3083

本文主要是介绍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;
}