竞赛讨论区 > 求大佬帮帮我%99.17
头像
shyyhs
发布于 2020-01-10 18:23
+ 关注

求大佬帮帮我%99.17


这个bfs代码还有什么问题哎,求个大神帮助
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <map>
#include <math.h>
#include <set>
#include <vector>
#define ll long long
const int INF = 0x3f3f3f3f;
const int NINF = -INF - 1;
using namespace std;
int vis[1005][1005];//标记是否走过
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};//四个方向
char an[1005][1005];//地图
int t,n,m;
struct node
{
  int x;
  int y;
  int step;
};
node temp,now,dd;
queue<node>q;
node a[1000005];//入口
node b[1000005];//出口
int check1(node w)
{
 for(int i=1;i<=t;i++)
 {
     if(w.x==a[i].x&&w.y==a[i].y)
     {
         return 1;
     }
     else if(w.x==b[i].x&&w.y==b[i].y)
     {
         return 1;
     }
 }
  return 0;
}

int check2(node p)
{
    if(!vis[p.x][p.y]&&p.x>=1&&p.x<=n&&p.y>=1&&p.y<=m&&an[p.x][p.y]!='#') return 1;
    else                                                                  return 0;
}

void bfs()
{
    while(q.size())
    {
        temp=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            now=temp;
            now.x=temp.x+dir[i][0];
            now.y=temp.y+dir[i][1];
            now.step++;
            dd=now;
            if(an[now.x][now.y]=='T')
            {
                printf("%d\n",now.step+(now.step-1)/8);
                return;
            }
            if(check1(now))
            {
                for(int i=1;i<=t;i++)
                {
                   if(now.x==a[i].x&&now.y==a[i].y)
                   {
                      dd.x=b[i].x;
                      dd.y=b[i].y;
                      vis[dd.x][dd.y]=1;
                      q.push(dd);
                   }
                    else if(now.x==b[i].x&&now.y==b[i].y)
                    {
                      dd.x=a[i].x;
                      dd.y=a[i].y;
                      vis[dd.x][dd.y]=1;
                      q.push(dd);
                    }
                }
            }
            if(check2(now))
            {
               vis[now.x][now.y]=1;
               q.push(now);
            }
        }
    }
    printf("-1\n");
}

int main()
{
    int x1,y1,x2,y2;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>an[i][j];
            if(an[i][j]=='S')
            {
                temp.x=i;
                temp.y=j;
                temp.step=0;
                vis[i][j]=1;
                q.push(temp);
            }
        }
    }//输入地图
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        a[i].x=x1;a[i].y=y1;
        b[i].x=x2;b[i].y=y2;
    }
    bfs();
    return 0;
}

全部评论

(2) 回帖
加载中...
话题 回帖