题解：CF88B Keyboard

Jayfeather2012 · 2025-02-02 18:53:51 · 题解

思路

一道模拟~~
我们定义一个 map 存字符是否可打出与是否需要右手。
根据题意，先遍历键盘，扫出所有 Shift 并存入数组中，再遍历一遍键盘，对于每个非 Shift 键，标记此小写字符可打出，对于它对应的大写字母，判断是否有一个 Shift 键与它的距离小于 x，若有，标记其可打出且不需右手，若没有，标记其可打出且需右手。
最后根据信息判断文本能否打出并统计需要右手的次数。
具体细节看代码吧！

代码

#include<bits/stdc++.h>
#define ll long long
#define pp pair<int,int>
using namespace std;
int n,m,q,t,ans;
long double f,x[905],y[905];
string s;
char a[35][35];
map<char,int>mp;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>f;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>a[i][j];
            if(a[i][j]=='S'){
            //是Shift键，存储其位置
                x[++t]=i;
                y[t]=j;
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            long double xx=i,yy=j;
            if(a[i][j]=='S')continue;
            //是Shift,不进行下面操作
            mp[a[i][j]]=1;
            //标记小写字母可打出
            if(mp[a[i][j]-'a'+'A']==1||!t)continue;
            //若已标记其可打出且不需右手或没有Shift键，不进行下面操作
            for(int k=1;k<=t;++k){
                if(sqrt(((xx-x[k])*(xx-x[k]))+((yy-y[k])*(yy-y[k])))<=f){
                //若距离小于等于x，标记其可打出且不需右手
                    mp[a[i][j]-'a'+'A']=1;
                    break;
                }
            }
            if(!mp[a[i][j]-'a'+'A'])mp[a[i][j]-'a'+'A']=2;
            //若距离都大于x，标记其不可打出且不需右手
        }
    }
    cin>>q>>s;
    for(int i=0;i<q;++i){
        if(mp[s[i]]==0){
            cout<<-1<<"\n";
            return 0;
            //不能打出输出-1并结束
        }
        if(mp[s[i]]==2)++ans;
        //若需要右手，增加需要右手的次数
    }
    cout<<ans;
    return 0;
}