AT_abc436_d 题解

· · 题解

看到这两条犇后，我在我的粉丝群 1039915194 里发了一句：

AT 自己重自己，牛的！

所以有双倍经验。但是为什么之前是 E 现在是 D！/fn

第一种移动是正常的，可以直接上 BFS 去弄；而第二种移动则麻烦一些，你得枚举所有和你相同的字母去转移。

但是我们发现，第二种移动的情况下，本质上每种字母只会被处理一次。因为我们跑的是 BFS，越先进队的次数越小，如果你这一次到了这个字母，你就会把所有这个字母的跑掉，因为再往后只会更劣。因此本质上还是 O(nm) 的。

于是就有了 BFS 的实现方法。正常移动正常做，如果在字母格子上，就遍历所有该字母的格子去转移，然后标记该字母已经被处理完毕。

由于我赛时脑子抽了，使用了 set 去存字母情况，其实 vector 应该也是可以的哈。

所以时间复杂度正常应该是 O(nm) 的，和我一样用 set 的话就是 O(nm\log{nm})，不过一只小 \log 影响不大。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 1e3+5;
int n,m,dis[N][N];
queue<pii> q;
char c[N][N];
bool vis[N][N];
set<pii> st[30];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            if(c[i][j]>='a'&&c[i][j]<='z')
                st[c[i][j]-'a'+1].insert({i,j});
        }
    memset(dis,0x3f,sizeof(dis));
    vis[1][1]=1,dis[1][1]=0,q.push({1,1});
    if(c[1][1]>='a'&&c[1][1]<='z')
        st[c[1][1]-'a'+1].erase({1,1});
    while(!q.empty()){
        auto [x,y]=q.front();q.pop();
        for(int i=0;i<4;i++){
            int x2=x+dx[i],y2=y+dy[i];
            if(x2<1||x2>n||y2<1||y2>m)continue;
            if(c[x2][y2]=='#')continue;
            if(vis[x2][y2])continue;
            dis[x2][y2]=dis[x][y]+1;
            vis[x2][y2]=1,q.push({x2,y2});
            if(c[x2][y2]>='a'&&c[x2][y2]<='z')
                st[c[x2][y2]-'a'+1].erase({x2,y2});
        }if(c[x][y]>='a'&&c[x][y]<='z'){
            for(auto [x2,y2]:st[c[x][y]-'a'+1]){
                dis[x2][y2]=dis[x][y]+1;
                vis[x2][y2]=1,q.push({x2,y2});
            }st[c[x][y]-'a'+1].clear();
        }
    }if(vis[n][m])cout<<dis[n][m]<<"\n";
    else cout<<"-1\n";
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！