这道题的题意,大致是说
给你一个n*m
的矩阵,矩阵里是字母
你从左上角
出发,你要使你的路径上包含
一个字符串
这个字符串就是题中的打印文本串s
当然,应题目要求,你的这个路径的结尾要以*
结尾
题中有一点不太好理解,就是说举个例子
AAAAAAZ
这是个键盘中的一行,你位于第一个A那里,你把光标向右挪一下后
你会到哪里?是第二个A吗?
NO!NO!NO!
你会到Z那里去!
分析完题目,我们来看怎么做
首先,可以想到暴力+贪心的做法:
从左上角出发,每次寻找最近的、字符串中的下一个字符
记录当前位置,继续寻找下一个字符……
这个做法不会超时,但是答案错
好吧,那就争取把全部计算都放进一次BFS中
可以开一个数组d[i][j][c]
,表示:
从左上角走到(i,j)
,已经经过了c
个目标字符串中的字符,用了多少步
剩下的就容易多了,但是坑点有一个:
千万不要用queue
,要手写数组模拟队列!否则会T三个点
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=55,M=10010;
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
struct node{
int x,y,c;
};
int n,m;
string s[N],T;
PII g[N][N][4];
int d[N][N][M];
node q[N*N*M];
int hh=0,tt=-1;
void init(){
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
for(int k=0;k<2;++k){
int x=i+dx[k],y=j+dy[k];
if(x && y && x<=n && y<=m){
if(s[i][j]!=s[x][y]) g[i][j][k]=make_pair(x,y);
else g[i][j][k]=g[x][y][k];
}
}
for(int i=n;i>=1;--i)
for(int j=m;j>=1;--j)
for(int k=2;k<4;++k){
int x=i+dx[k],y=j+dy[k];
if(x && y && x<=n && y<=m){
if(s[i][j]!=s[x][y]) g[i][j][k]=make_pair(x,y);
else g[i][j][k]=g[x][y][k];
}
}
}
int bfs(){
memset(d,0x3f,sizeof(d));
d[1][1][0]=0;
if(s[1][1]==T[0]){
q[++tt]={1,1,1};
d[1][1][1]=0;
}
else{
q[++tt]={1,1,0};
d[1][1][0]=0;
}
while(hh<=tt){
node t=q[hh++];
if(s[t.x][t.y]==T[t.c]){
d[t.x][t.y][t.c+1]=d[t.x][t.y][t.c];
q[++tt]={t.x,t.y,t.c+1};
continue;
}
for(int i=0;i<4;++i){
int xx=g[t.x][t.y][i].x,yy=g[t.x][t.y][i].y;
if(!(xx && yy && xx<=n && yy<=m)) continue;
int C=t.c;
if(s[xx][yy]==T[C]) C++;
if(d[xx][yy][C]<=d[t.x][t.y][t.c]+1) continue;
//cout<<xx<<" "<<yy<<" "<<C<<":::"<<endl;
d[xx][yy][C]=d[t.x][t.y][t.c]+1;
q[++tt]={xx,yy,C};
//cout<<d[xx][yy][C]<<" "<<T.size()<<" "<<C<<endl;
if(C==T.size()) return d[xx][yy][C]+T.size();
}
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>s[i];
s[i]='-'+s[i];
}
init();
cin>>T;
T+='*';
cout<<bfs()<<endl;
return 0;
}