1 条题解

  • 0
    @ 2025-10-8 16:57:15

    ycy代码:

    #include<bits/stdc++.h>
    using namespace std;
    int n;
    int timex[200][200]={0};
    int xx,yy,sx,sy,ex,ey;
    int dx[4]={-1,0,1,0};
    int dy[4]={0,1,0,-1};
    queue<int>quex,quey;
    char mapx[200][200]={0};
    bool teller[4]={1};
    int main()
    {
        memset(timex,-1,sizeof(timex));
        scanf("%d",&n);
        getchar();
        for (int i=0;i<n;i++) for (int j=0;j<n;j++) 
        {
            cin>>mapx[i][j];
            if (mapx[i][j]=='A'){sx=i;sy=j;}
            if (mapx[i][j]=='B'){ex=i;ey=j;mapx[i][j]='.';}
        }
        quex.push(sx); quey.push(sy); 
        while (quex.size()>0)
        {
            memset(teller,1,sizeof(teller));
            xx=quex.front(); yy=quey.front();
            if (xx==ex && yy==ey)
            {
                cout<<timex[ex][ey]<<endl;
                return 0;
            }
            for (int j=0;j<=3;j++)
            {
                for (int i=1;i<=n;i++) if (teller[j]==1)
                {
                    if (xx+dx[j]*i>=0 && xx+dx[j]*i<n && yy+dy[j]*i>=0 && yy+dy[j]*i<n)
                    {
                        if (mapx[xx+dx[j]*i][yy+dy[j]*i]=='.' && timex[xx+dx[j]*i][yy+dy[j]*i]==-1) 
                        {
                            timex[xx+dx[j]*i][yy+dy[j]*i]=timex[xx][yy]+1;
                            quex.push(xx+dx[j]*i); quey.push(yy+dy[j]*i);
                        }
                        else if (mapx[xx+dx[j]*i][yy+dy[j]*i]=='x') teller[j]=0;
                    }
                    else teller[j]=0;
                }
            }
            quex.pop(); quey.pop();
        }
        cout<<-1<<endl; 
        return
    • 1

    *【宽搜】矩阵最少转90度次数[USACO07OCT] Obstacle Course S

    信息

    ID
    1440
    时间
    1000ms
    内存
    128MiB
    难度
    6
    标签
    递交数
    86
    已通过
    25
    上传者