AT_abc436_d [ABC436D] Teleport Maze 题解

· · 题解

洛谷传送门 | AT 传送门

题外话：锣鼓咕值系统大更新，昔日 100 比赛的我掉到了 37……只能写写题解攒攒咕了。

简单搜索题。

题意：给定一个 n\times m 的地图，初始小人在 (1,1)，且体力值为 0，他想走到 (n,m) 去。地图中一个点若不是 # 则表示此地通畅，可以增加 1 点体力走到上下左右的四个点上。若这个点是小写字母，则可以增加 1 点体力传送到任意一个有着同样小写字母的点上。小人想知道他最少需多少体力。

这种题很典啊就是一个 bfs 搜索，可这题的难点是传送。

如果每次到达一个小写字母点就都搜索一遍相同字母点，这样的话很明显会被卡（TLE*14）。可以发现如果第一次走到了一个标着 a 的点，那么所有标着 a 的点都会被搜索一遍，以后再遇到标着 a 的点就不用再跳到其他标着 a 的点了。

所以，可以发现每个字母只会枚举相同字母点 1 次。然后就解决了。

#include<bits/stdc++.h>
//#define endl '\n'
#define lowbit(x) (x)&(-x)
using namespace std;

typedef double db;
typedef long long ll;
typedef __int128 III;
const db eps=1e-6;
const int inf=1e9;
void ll_cmax(ll &a,ll b){a=a>b?a:b;}
void ll_cmin(ll &a,ll b){a=a<b?a:b;}
void int_cmax(int &a,int b){a=a>b?a:b;}
void int_cmin(int &a,int b){a=a<b?a:b;}
bool db_eq(db a,db b){return fabs(a-b)<eps;}
bool number(char ch){return ch>='0' && ch<='9';}
bool lower(char ch){return ch>='a' && ch<='z';}
bool capit(char ch){return ch>='A' && ch<='Z';}
int sqlong(int n){int sq=sqrt(n)+1;return min(sq,n);}

const int MAXN=1000+5;
char a[MAXN][MAXN];
string s;
int n,m,v[30],b[MAXN][MAXN];
vector<pair<int,int> >k[30];
queue<pair<pair<int,int>,int> >q;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        for(int j=0;j<m;j++) 
        {
            a[i][j+1]=s[j];
            if(lower(s[j])) k[s[j]-'a'].push_back({i,j+1}); 
        }
    }
    for(int i=0;i<=n+1;i++) a[i][0]=a[i][m+1]='#';
    for(int i=0;i<=m+1;i++) a[0][i]=a[n+1][i]='#';
    q.push({{1,1},0});
    b[1][1]=1;
    int ans=inf;
    while(q.size())
    {
        pair<int,int>x=q.front().first;int p=q.front().second;q.pop();
//      cout<<x.first<<" "<<x.second<<endl;
//      b[x.first][x.second]=0;
        if(x.first==n && x.second==m) 
        {
            int_cmin(ans,p);
            continue;
        }
        if(a[x.first+1][x.second]!='#' && !b[x.first+1][x.second]) b[x.first+1][x.second]=1,q.push({{x.first+1,x.second},p+1});
        if(a[x.first-1][x.second]!='#' && !b[x.first-1][x.second]) b[x.first-1][x.second]=1,q.push({{x.first-1,x.second},p+1});
        if(a[x.first][x.second+1]!='#' && !b[x.first][x.second+1]) b[x.first][x.second+1]=1,q.push({{x.first,x.second+1},p+1});
        if(a[x.first][x.second-1]!='#' && !b[x.first][x.second-1]) b[x.first][x.second-1]=1,q.push({{x.first,x.second-1},p+1});
        if(lower(a[x.first][x.second]) && !v[a[x.first][x.second]-'a'])
        {
            v[a[x.first][x.second]-'a']=1;
            for(int i=0;i<k[a[x.first][x.second]-'a'].size();i++) 
            {
                if(!b[k[a[x.first][x.second]-'a'][i].first][k[a[x.first][x.second]-'a'][i].second])
                {
                    b[k[a[x.first][x.second]-'a'][i].first][k[a[x.first][x.second]-'a'][i].second]=1;
                    q.push({{k[a[x.first][x.second]-'a'][i].first,k[a[x.first][x.second]-'a'][i].second},p+1}); 
                }
            }
        }
    }
    if(ans==inf) cout<<-1<<endl;
    else cout<<ans<<endl;
    return 0;
}
//by Matrix_Power

AC 记录