# #10030. 「一本通 1.4 练习 2」Keyboarding
【题目描述】
给定一个 $r$ 行 $c$ 列的在电视上的“虚拟键盘”，通过「上，下，左，右，选择」共 $5$ 个控制键，你可以移动电视屏幕上的光标来打印文本。一开始，光标在键盘的左上角，每次按方向键，光标总是跳到下一个在该方向上与当前位置不同的字符，若不存在则不移动。每次按选择键，则将光标所在位置的字符打印出来。
现在求打印给定文本（要在结尾打印换行符）的最少按键次数。
【算法】
1、预处理四个方向能到达的点。
2、$bfs$ 判重记录状态：
v[i][j]数组记录在（i，j）位置已打印的字符个数，判重：若当前位于（i，j）点将要处理第n个字符则能进入队列的条件是n>v[i][j]
3、1个小优化：
若当前状态和待处理字符匹配，则不打印而继续向四个方向延申的操作肯定非最优
【代码】
#include <bits/stdc++.h>
using namespace std;
struct state{ int x,y,num,step; }st;
int r,c,all,ans;
int a[55][55][4],v[55][55];
char s[55][55],res[10100];
queue<state> q;
const int dx[4]={ -1,0,1,0 },dy[4]={ 0,1,0,-1 };
void parse() {
for(int i=1;i<=r;i++) {
for(int j=1;j<=c;j++) {
for(int k=0;k<4;k++) {
int nx=i,ny=j,t=0;
while(nx>=1&&nx<=r&&ny>=1&&ny<=c) {
if(s[nx][ny]!=s[i][j]) break;
nx+=dx[k],ny+=dy[k],t++;
}
if(nx>=1&&nx<=r&&ny>=1&&ny<=c) a[i][j][k]=t;
}
}
}
}
void bfs() {
v[1][1]=1;
q.push((state){ 1,1,1,0 });
while(q.size()) {
state next,now=q.front(); q.pop();
if(s[now.x][now.y]==res[now.num]&&v[now.x][now.y]<now.num+1) {
v[now.x][now.y]=now.num+1;
next=(state){ now.x,now.y,now.num+1,now.step+1 };
if(next.num>all) { ans=next.step; break; }
q.push(next);
}
else for(int i=0;i<4;i++) {
int bias=a[now.x][now.y][i];
if(bias) {
next=(state){ now.x+bias*dx[i],now.y+bias*dy[i],now.num,now.step+1 };
if(v[next.x][next.y]>=next.num) continue;
v[next.x][next.y]=next.num;
q.push(next);
}
}
}
}
int main() {
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++) scanf("%s",s[i]+1);
scanf("%s",res+1); res[strlen(res+1)+1]='*';
all=strlen(res+1);
parse();
bfs();
printf("%d
",ans);
return 0;
}