做了1天,总是各种错误,很无语
最后还是参考大神的方法
题目:http://poj.org/problem?id=3083
题意:从s到e找分别按照左侧优先和右侧优先的最短路径,和实际的最短路径
DFS找左右侧 的最短路径
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
char G[][];
int vis[][];
int c,r;
struct node
{
int x,y,dis;
}s,pos,next; int dx[]= {,-,,};
int dy[]= {-,,,};
int dfs(int x,int y,int f,char ch)//这题dfs是重点,f表示当前的朝向
{
int i,j,nx,ny,nf;
if(G[x][y]=='E')
return ;
if(ch=='l')
{
for(i=f-; i<f+; i++)
{
nx=x+dx[(i+)%];
ny=y+dy[(i+)%];
nf=(i+)%;
if(nx>=&&nx<r&&ny>=&&ny<c&&G[nx][ny]!='#')
return dfs(nx,ny,nf,ch)+;
}
}
else if(ch=='r')
{
for(i=f+; i>f-; i--)
{
nx=x+dx[(i+)%];
ny=y+dy[(i+)%];
nf=(i+)%;
if(nx>=&&nx<r&&ny>=&&ny<c&&G[nx][ny]!='#')
return dfs(nx,ny,nf,ch)+;
}
}
return ;
} int bfs(int x,int y)
{
queue<node>q;
int i;
memset(vis,,sizeof(vis));
next.dis=; next.x=x; next.y=y;
vis[x][y]=;
q.push(next);
while(!q.empty())
{
pos=q.front();
q.pop();
for(i=; i<; i++)
{
next.x=pos.x+dx[i]; next.y=pos.y+dy[i];
next.dis=pos.dis+;
if(next.x>=&&next.x<r&&next.y>=&&next.y<c&&G[next.x][next.y]!='#'&&vis[next.x][next.y]==)
{
q.push(next);
vis[next.x][next.y]=;
if(G[next.x][next.y]=='E')
return next.dis;
}
}
}
return ;
}
int main()
{
int i,j,t;
int le,ri,f,ans,flag;
cin>>t;
while(t--)
{
cin>>c>>r;
for(i=; i<r; i++)
cin>>G[i];
flag=;
for(i=; i<r; i++)
{
for(j=; j<c; j++)
if(G[i][j]=='S')
{
s.x=i;
s.y=j;
s.dis=;
if(i==)
f=;
else if(i==r-)
f=;
else if(j==)
f=;
else if(j==c-)
f=;
flag=;
break;
}
if(flag)
break;
}
le=dfs(s.x,s.y,f,'l');
ri=dfs(s.x,s.y,f,'r');
ans=bfs(s.x,s.y);
printf("%d %d %d\n",le,ri,ans);
}
return ;
}