UVA1714 Keyboarding

读题读了十多分钟才读懂，辣鸡ybt翻译。

需要注意的关于题意的点：

1. 移动和点击都要算作次数
2. 最后还要打印*换行符
3. 每个方向直接移动到最近的不同的点，如果没有就不移动

做法就是基础的bfs，不过需要预处理一下每个点向四个方向移动的下一个点，直接暴力做即可。

剪枝是如果当前在打印文本的位置 $>$ 之前搜索过的同一个点位置就退出。

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

pr to[55][55][4];
int n,m,len,vis[55][55];
char s[55][55],goal[10005];
struct node{int x,y,cnt,ans;};
int fx[4]={0,1,0,-1},fy[4]={1,0,-1,0};

inline void get_to() //预处理
{
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            for (int k=0;k<4;k++)
            {
                int x=i+fx[k],y=j+fy[k];
                while (x>=1 && x<=n && y>=1 && y<=m && s[x][y]==s[i][j])
                {
                    x+=fx[k];
                    y+=fy[k];
                }
                if (x<1 || x>n || y<1 || y>m) continue;
                to[i][j][k]=mp(x,y);
            }
        }
    }
}

inline int bfs()
{
    queue <node> q;
    int i=1;
    while (goal[i]==s[1][1]) i++; //能在第一个位置打印的先打印完
    q.push((node){1,1,i,i-1});
    vis[1][1]=i;
    while (!q.empty())
    {
        node now=q.front(); q.pop();
        if (s[now.x][now.y]==goal[now.cnt])
        {
            now.ans++;
            if (now.cnt==len) return now.ans;
            now.cnt++;
            vis[now.x][now.y]=now.cnt;
            q.push(now);
            continue;
        }
        for (int i=0;i<4;i++)
        {
            int tx=to[now.x][now.y][i].first,ty=to[now.x][now.y][i].second;
            if (!tx || !ty) continue;
            if (vis[tx][ty]>=now.cnt) continue; //剪枝
            vis[tx][ty]=now.cnt;
            q.push((node){tx,ty,now.cnt,now.ans+1});
        }
    }
    return 0;
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
    scanf("%s",goal+1);
    len=strlen(goal+1);
    goal[++len]='*';
    get_to();
    printf("%d",bfs()); 
    return 0;
}