ACM BFS最短路(考虑方向)初始方向如何确定

Question

这是一道DFS 与 BFS的代码

#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#include<cmath>  
#include<stack>  
#include<map>  
#include<vector>  
#include<queue>  
using namespace std;  
#define mp make_pair  
#define x first  
#define y second  
const int INF=0x3f3f3f3f;  
const int N=111;  
typedef pair<int,int>pii;  
typedef pair<int,pii>pi;  
char g[N][N];  
bool vis[N][N];  
int d[4][2]={{0,-1},{-1,0},{0,1},{1,0}};  
int n,m;  
int dfsl(int x,int y,int dir)  
{  
    if(g[x][y]=='E')return 1;  
    for(int i=dir-1;i<=dir+2;i++){  
        int k=(i+4)%4;  
        int xx=x+d[k][0],yy=y+d[k][1];  
        if(xx<0||yy<0||xx==n||yy==m)continue;  
        if(g[xx][yy]!='#')return dfsl(xx,yy,k)+1;  
    }  
}  
int dfsr(int x,int y,int dir)  
{  
    if(g[x][y]=='E')return 1;  
    for(int i=dir+1;i>=dir-2;i--){  
        int k=(i+4)%4;  
        int xx=x+d[k][0],yy=y+d[k][1];  
        if(xx<0||yy<0||xx==n||yy==m)continue;  
        if(g[xx][yy]!='#')return dfsr(xx,yy,k)+1;  
    }  
}  
int bfs(int x,int y)  
{  
    queue<pi>q;  
    memset(vis,0,sizeof(vis));  
    q.push(mp(1,mp(x,y)));  
    vis[x][y]=1;  
    while(!q.empty()){  
        pi t=q.front();q.pop();  
        int step=t.first;  
        x=t.second.x; y=t.second.y;  
        if(g[x][y]=='E')return step;  
        for(int i=0;i<4;i++){  
            int xx=x+d[i][0],yy=y+d[i][1];  
            if(g[xx][yy]!='#'&&!vis[xx][yy])q.push(mp(step+1,mp(xx,yy))),vis[xx][yy]=1;  
        }  
    }  
    return -1;  
}  
int main()  
{  
    pii start,endd;  
    int T;scanf("%d",&T);  
    while(T--){  
        scanf("%d%d",&m,&n);  
        for(int i=0;i<n;i++){  
            scanf("%s",g[i]);  
            for(int j=0;j<m;j++)  
                if(g[i][j]=='S')start=mp(i,j);  
                else if(g[i][j]=='E')endd=mp(i,j);  
        }  
        int dir;  
        if(start.x==n-1)dir=1;  
        else if(start.y==m-1)dir=0;  
        else if(start.x==0)dir=3;  
        else dir=2;  
        printf("%d %d %d\n",dfsl(start.x,start.y,dir),dfsr(start.x,start.y,dir),bfs(start.x,start.y));  
    }  
    return 0;  
}  

请问主函数

```int main()

{

pii start,endd;

int T;scanf("%d",&T);

while(T--){

scanf("%d%d",&m,&n);

for(int i=0;i<n;i++){

scanf("%s",g[i]);

for(int j=0;j<m;j++)

if(g[i][j]=='S')start=mp(i,j);

else if(g[i][j]=='E')endd=mp(i,j);

}

int dir;

if(start.x==n-1)dir=1;

else if(start.y==m-1)dir=0;

else if(start.x==0)dir=3;

else dir=2;

printf("%d %d %d\n",dfsl(start.x,start.y,dir),dfsr(start.x,start.y,dir),bfs(start.x,start.y));

}

return 0;

}

初始方向 dir 是如何确定的

Answer 1

能不能把问题粘一下？那个T是指的走几步么？