题解 P6909 【[ICPC2015 WF]Keyboarding】

· · 题解

坑点提醒

1、最后需要你手动添加一个“*”

2、注意在其实位置按键的情况

思路

首先我们可以把所有相关涉及到的字符都映射为数字，方便处理，包括(A…Z),(1…9),("*""-")这些东东，处理的时候别映射 0 就行

当我们输入的时候直接映射到一个二维数组 a 来装载键盘的每个键

将目标串映射到一个一维数组 b 中来需要按得每一个键，最后别忘了手动添加一位来存 "*"

那么如何选择位置呢，如果在搜索的过程中暴力美剧会非常耗时间，那么这个时候就可以预处理每一个键第一个到达的位置即可

为了方便我们要设一个结构体类型的三维数组

结构体的变量分别为 到达的位置的横坐标 x ,到达位置的纵坐标 y ,到达这个位置的时候要匹配目标串的哪一位 step ,以及到这个点已经走了几步 dis

三维数组 f[k][i][j] 表示从 (i,j)向 k 方向走到达的第一个位置的信息（即结构体中的内容）

那么预处理之后就开始广搜了

在开始广搜之前，因为我们是从第一位开始的，那么我们最好先预处理一下在第一位一共可以连续按几次，然后再把结构体重所表示的数据存进去，在代码中有就不详细说了

那么现在开始广搜

考虑两种情况，我们要把选择和匹配分开找

一、

那么先是匹配，要看一下堆顶的这个位置是否和当前要匹配的位置相同，如果是相同的时候，那就在进行判断一下这个是不是最终状态，如果是，那直接把答案赋值为当前的步数+1就是最有的答案

那如果不是最后的一个情况呢

可以设一个 vis 数组，用来存当前堆顶的点接下来该匹配哪一位了，然后把相应的结构体中的数据都放进去继续查找

二、

最后再开始选择

首先枚举该点四个位置的到达点，当然因为我在预处理位置的时候有一个位置得移动忘加了，所以还要加上，一次移动

首先判断一下是否越界

然后再判断一下当前要选择的地方要比原坐标的要处理的位置要更大，那么就不需要更新 vis 数组。

否则的话，就更新当前的 vis 数组为现在要处理的位置（不用+1，因为是选择，即跳过当前的匹配直接跳进），然后把当前要选择的位置的数据放进去

最后直接输出即可

代码实现

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
using namespace std;
const int N=59;
const int M=10009;
struct node{
    int x;
    int y;
    int step;//指下一个到了第几个位置， 
    int dis;//按了几次 
}f[5][N][N];//后两个表示坐标，前一个表示方向，即i,j在k方向上到的最近的点 
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char wor[M];
int n,m,len,a[N][N],b[M],vis[N][N];
map<char,int> mp;
void prepare()//预先将所有的字符串处理成数字类型的，方便处理
{
    for(int i=0;i<=9;i++)
    mp[(char)('0'+i)]=i+1;
    for(int i=0;i<26;i++)
    mp[(char)('A'+i)]=i+11;//1-10被取过了 
    mp['-']=37;
    mp['*']=38; 
} 
void get()//处理一下四个方向可以到达的点 
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=0;k<4;k++)
            {
                int x=i;
                int y=j;
                while(a[x][y]==a[x+dx[k]][y+dy[k]])//如果一致的话 
                {
                    x+=dx[k];
                    y+=dy[k];//一致加到不同为止 
                }
                f[k][i][j]=(node){x,y,0,0};
            }
}
int search()
{
    memset(vis,0,sizeof(vis));
    queue<node> q;
    int ans=0;
    int k=1;
    while(a[1][1]==b[k]&&k<=len) ++k;//在起点选取的情况
    q.push((node){1,1,k,k-1});
    vis[1][1]=k;
    while(!q.empty())
    {
        node cun=q.front();
        q.pop();
        int x=cun.x;
        int y=cun.y;
        int now=cun.step; 
        if(a[x][y]==b[now])//此时相等了
        {
            if(now==len) 
            {
                ans=cun.dis+1;
                break;//如果找完了？直接跳出 
            }
            vis[x][y]=now+1;//更新一下，因为按了一遍键盘 
            q.push((node){x,y,now+1,cun.dis+1});
        } 
        for(int i=0;i<4;i++)
        {
            node chose=f[i][x][y];
            chose.x+=dx[i];
            chose.y+=dy[i];//预处理上在加一次，保证完整
            if(chose.x<1||chose.x>n||chose.y<1||chose.y>m) continue;//越界了
            if(vis[chose.x][chose.y]>=now) continue;//如果选择的地方的要处理的位置比现在的要大，不用改，防止变worse 
            vis[chose.x][chose.y]=now;//如果可行，那么把接下来要弄得位置给存进去
            q.push((node){chose.x,chose.y,now,cun.dis+1});//跳到那一步 
        } 
    } 
    return ans;
}
int main()
{
    prepare();
    while(scanf("%d",&n)!=EOF)//UVA经典输入方式
    {   
//      cin>>n;
        cin>>m;
        for(int i=1;i<=n;i++)//输入每一行的字符串
        {
            cin>>wor;       
            for(int j=0;j<m;j++)
                a[i][j+1]=mp[wor[j]];//将每个字符的代表的数字映射到a数组中
                //从1开始方便 
        } 
        cin>>wor;
        len=strlen(wor);
        for(int i=0;i<len;i++) b[i+1]=mp[wor[i]];//依旧是映射，从1开始
        len++;
        b[len]=38;//注意最后有一个*
        get();
        cout<<search()<<endl; 
    } 
    return 0;
}