Submission #71676009

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
string s[maxn];
const int x[4]={-1,0,1,0};
const int y[4]={0,1,0,-1};
int ans[maxn][maxn];
vector<pair<int,int>> loc[30];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int h,w;
    cin>>h>>w;
    for (int i=1;i<=h;i++)
    {
        cin>>s[i];
        s[i]=' '+s[i];
        for (int j=1;j<=w;j++)
        {
            if (s[i][j]>='a'&&s[i][j]<='z')
                loc[s[i][j]-'a'].push_back({i,j});
        }
    }
    deque<pair<int,int>> q;
    q.push_back({1,1});
    ans[1][1]=1;
    while(!q.empty())
    {
        auto now=q.front();
        q.pop_front();
        if (now.first==h&&now.second==w)
        {
            cout<<ans[h][w]-1;
            return 0;
        }
        if (now.first)
        {
            for (int i=0;i<4;i++)
            {
                pair<int,int> nxt={now.first+x[i],now.second+y[i]};
                if (nxt.first>0&&nxt.first<=h&&nxt.second>0&&nxt.second<=w&&!ans[nxt.first][nxt.second]&&s[nxt.first][nxt.second]!='#')
                {
                    ans[nxt.first][nxt.second]=ans[now.first][now.second]+1;
                    q.push_back(nxt);
                }
            }
            if (s[now.first][now.second]>='a'&&s[now.first][now.second]<='z'&&!ans[0][s[now.first][now.second]-'a'])
            {
                ans[0][s[now.first][now.second]-'a']=ans[now.first][now.second];
                q.push_front({0,s[now.first][now.second]-'a'});
            }
        }
        else
        {
            for (auto i:loc[now.second])
            {
                if (!ans[i.first][i.second])
                {
                    ans[i.first][i.second]=ans[now.first][now.second]+1;
                    q.push_back(i);
                }
            }
        }
    }
    cout<<-1;
}

Submission Info

Judge Result