70分……大佬们啊啊啊啊啊啊啊啊!!!!
查看原帖
70分……大佬们啊啊啊啊啊啊啊啊!!!!
191248
Genshineer楼主2020/7/9 22:56

只有70分,不知道哪里出了问题

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x;
    int y;
    int d;
    int t;
};
int MIN=100000,flag=0,n,m,bx,by,ex,ey,fx[5][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0}},a[55][55],vis[55][55];
char dbeg;
void bfs(int beg)
{
    if(bx==ex&&by==ey)
    {
        flag=2;
        cout<<0<<endl;
        return;
    }
    node temp1;
    temp1.x=bx;
    temp1.y=by;
    temp1.d=beg;
    temp1.t=0;
    vis[bx][by]=1;
    queue<node> q;
    q.push(temp1);
    while(!q.empty())
    {
        node temp2=q.front();
        q.pop();
        if(temp2.x==ex&&temp2.y==ey)
        {
            MIN=min(MIN,temp2.t);
            flag=1;
        }
        for(int i=1;i<=4;i++)
        {
            int step=temp2.t;
            if(temp2.d!=i)
            {
                step++;
                if((i==1&&temp2.d==2)||(i==2&&temp2.d==1)||(i==3&&temp2.d==4)||(i==4&&temp2.d==3))
                    step++;
            }
            for(int j=1;j<=3;j++)
            {
                int dx=temp2.x+j*fx[i][0];
                int dy=temp2.y+j*fx[i][1];
                if(dx>n||dy>m||dx<1||dy<1||a[dx][dy])
                    break;
                if(vis[dx][dy]>step)
                {
                    vis[dx][dy]=step;
                    temp1.x=dx;
                    temp1.y=dy;
                    temp1.d=i;
                    temp1.t=step+1;
                    q.push(temp1);
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j])
            {
                a[i-1][j-1]=1;
                a[i-1][j]=1;
                a[i][j-1]=1;
            }
        }
    for(int i=1;i<=n;i++)
    {
        a[n][i]=1;
        a[i][m]=1;
    }
    cin>>bx>>by>>ex>>ey>>dbeg;
    memset(vis,0x3f3f3f3f,sizeof(vis));
    int beg;
    if(dbeg=='E')
        beg=1;
    if(dbeg=='W')
        beg=2;
    if(dbeg=='S')
        beg=3;
    else
        beg=4;
    bfs(beg);
    if(flag==0)
        cout<<-1;
    else
        cout<<MIN;
}
2020/7/9 22:56
加载中...