qq_33312212 2016-08-16 09:52 采纳率: 21.9%
浏览 1304
已结题

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

这是一道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 是如何确定的


  • 写回答

1条回答 默认 最新

  • 兰前小驻 2016-08-17 02:35
    关注

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

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题