1 solutions

  • 0
    @ 2025-11-5 18:05:38

    C++ :

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    #include <climits>
    #include <cstring>
    #include <string>
    #include <set>
    #include <map>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <list>
    #include <ext/rope>
    #define rep(i,m,n) for(i=m;i<=n;i++)
    #define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
    #define vi vector<int>
    #define pii pair<int,int>
    #define mod 1000000007
    #define inf 0x3f3f3f3f
    #define pb push_back
    #define mp make_pair
    #define fi first
    #define se second
    #define ll long long
    #define pi acos(-1.0)
    const int maxn=1e2+10;
    const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
    using namespace std;
    using namespace __gnu_cxx;
    ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
    ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
    int n,m,k,ans,vis[maxn][maxn],poe[maxn][maxn];
    char a[maxn][maxn];
    struct node
    {
        int x,y,now,vis;
        node(int a,int b,int c,int d)
        {
            x=a,y=b,now=c,vis=d;
        }
        bool operator<(const node&p)const
        {
            return vis>p.vis;
        }
    };
    void bfs(int f,int g)
    {
        node init(f,g,k,1);
        priority_queue<node>p;
        p.push(init);
        vis[f][g]=1;poe[f][g]=k;
        while(!p.empty())
        {
            node q=p.top();p.pop();
            int x=q.x,y=q.y;
            for(int i=0;i<4;i++)
            {
                int l=x+dis[i][0],r=y+dis[i][1];
                if(l>=0&&l<n&&r>=0&&r<m)
                {
                    if(a[l][r]=='#'&&q.now&&(!vis[l][r]||vis[l][r]>vis[x][y]+3||poe[l][r]<poe[x][y]-1))
                    {
                        node u(l,r,q.now-1,q.vis+3);
                        poe[l][r]=q.now-1;
                        vis[l][r]=vis[x][y]+3;
                        p.push(u);
                    }
                    if(a[l][r]=='.'&&(!vis[l][r]||vis[l][r]>vis[x][y]+1||poe[l][r]<poe[x][y]))
                    {
                        node u(l,r,q.now,q.vis+1);
                        poe[l][r]=q.now;
                        vis[l][r]=vis[x][y]+1;
                        p.push(u);
                    }
                    if(a[l][r]=='E')ans=min(q.vis,ans);
                }
            }
        }
    }
    int main()
    {
        int i,j;
        scanf("%d%d%d",&n,&m,&k);
        ans=1e9;
        rep(i,0,n-1)scanf("%s",a[i]);
        rep(i,0,n-1)rep(j,0,m-1)
            if(a[i][j]=='B'){bfs(i,j);goto loop;}
        loop:;
        if(ans!=1e9)printf("%d\n",ans);
        else puts("-1");
        //system ("pause");
        return 0;
    }
    
    • 1

    Information

    ID
    18777
    Time
    1000ms
    Memory
    64MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By