题解

1 条题解

  • 0
    @ 2022-08-31 20:10:14
    #include<iostream>
    using namespace std;
    const int N=101;
    int n,m,r,a[N][N];
    bool flag=false;
    int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
    bool shit[N][N][N];
    struct node
    {
        int x,y,num,time;
    }h[10000001];
    void sb()
    {
        int head=0,tail=1;
        h[1].x=1,h[1].y=1,h[1].num=0,h[1].time=0;
        shit[1][1][0]=1;
        while(head<tail)
        {
            head++;
            for(int i=1;i<=4;i++)
        {
            int xx,yy;
            for(int j=1;j<=n;j++)
            {
                xx=h[head].x+dx[i]*j,yy=h[head].y+dy[i]*j;
                if(xx<1||xx>n||yy<1||yy>m)
                {
                    break;
                }
                if(a[xx][yy]==1)
                {
                    continue;
                }
                tail++;
                h[tail].x=xx,h[tail].y=yy;
                h[tail].num=h[head].num,h[tail].time=h[head].time+1;
                if(j>1)
                {
                    h[tail].num+=j;
                }
                if(h[tail].num>r)
                {
                    tail--;
                    break;
                }
                if(shit[xx][yy][h[tail].num]==1)
                {
                    tail--;
                    continue;
                }
                shit[xx][yy][h[tail].num]=1;
                if(xx==n&&yy==m)
                {
                    cout<<h[tail].time;
                    flag=true;
                    return ;
                }
            }
        }
        }
    }
    int main()
    {
        cin>>n>>m>>r;
        char c;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>c;
                if(c=='P')
                {
                    a[i][j]=0;
                }
                else
                {
                    a[i][j]=1;
                }
            }
        }
        sb();
        if(!flag)
        {
            cout<<"Impossible";
        }
        return 0;
    }
    
  • 1

信息

ID
1607
难度
7
分类
搜索 点击显示
标签
递交数
10
已通过
2
通过率
20%
上传者