bfs
坑点很多的一题（由于一本通的辣鸡翻译会错题意*n）。
1.多组数据
2.如果某方向上没有不同字符光标不会动
我们每次预处理出每个点向四个方向下次到达的点。然后跑bfs即可
注意bfs每次只能扩展一层（也就是说距离dis每次最多只能+1，否则无法保证最优性）！（所以不要把移动和选择写到一起qwq）
处理字符用map就好了
（卡了我一整天qwq）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
inline int mini(int &a,int &b) {return a<b ?a:b;}
int d1[]={,,,-};
int d2[]={,,-,};
int n,m,len,a[][],b[],vis[][];
struct data{int x,y,step,dis;}dir[][][];
map <char,int> Map;
void draw(){ //字符处理成数字好写
for(int i=;i<=;++i) Map[(char)(''+i)]=i+;
for(int i=;i<;++i) Map[(char)('A'+i)]=i+;
Map['-']=; Map['*']=;
}
void pretreatment(){ //预处理四个方向上下次可到的点
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
for(int k=;k<;++k){
int r1=i,r2=j;
while(a[r1][r2]==a[r1+d1[k]][r2+d2[k]]) r1+=d1[k],r2+=d2[k];
dir[k][i][j]=(data){r1,r2,,};
}
}
inline int bfs(){
memset(vis,,sizeof(vis));
queue <data> h; int ans=;
int k=;
while(b[k]==a[][]&&k<=len) ++k;
h.push((data){,,k,k-}); vis[][]=k; //特判在起点选取的情况
while(!h.empty()){
data u=h.front(); h.pop();
if(a[u.x][u.y]==b[u.step]){ //选择（千万不能和移动写在一起）
if(u.step==len) {ans=u.dis+; break;}
vis[u.x][u.y]=u.step+;
h.push((data){u.x,u.y,u.step+,u.dis+});
continue;
}
for(int i=;i<;++i){
data to=dir[i][u.x][u.y]; to.x+=d1[i]; to.y+=d2[i]; //由于我的预处理没写完整要再加一次
if(to.x<||to.x>n||to.y<||to.y>m) continue;
if(vis[to.x][to.y]>=u.step) continue;
vis[to.x][to.y]=u.step;
h.push((data){to.x,to.y,u.step,u.dis+});
}
}
return ans;
}
int main(){
//freopen("UVA1714.in","r",stdin);
draw();
char q[];
while(scanf("%d",&n)!=EOF) //多组数据
{
scanf("%d",&m);
for(int i=;i<=n;++i){
scanf("%s",q);
for(int j=;j<m;++j) a[i][j+]=Map[q[j]];
}
scanf("%s",q); len=strlen(q);
for(int i=;i<len;++i) b[i+]=Map[q[i]];
b[++len]=; //b数组存操作串
pretreatment();
printf("%d\n",bfs());
}
return ;
}