代码在acwing的测评机上会超时,但是在牛客或者是下面这个正统的测评网站的测评机上却能过
传送门2:信息学奥赛一本通上的测评机
思路:看别人的一些题解没能看懂,但去找了一些大佬的代码看了反而更加直白。
首先题意的理解很重要,审题不审全直接看样例看了很久,直到看到“光标总是跳到下一个在该方向上与当前位置不同的字符”这句话我才明白样例究竟是这么来的。
看的那份代码的大佬的做法
第一步:预处理出每一个PII [x,y,k]类型的next数组,用来表示在[x,y]这个点上方向k的下一个节点应该跳到哪一个节点,这样在bfs时,扩展每一个点的四个方向就可以直接跳了,
第二步:开始做bfs, 存一个结构体{x,y,dix,stp}作为每一个状态,表示走到节点[x,y]的距离,还有stp表示当前应该查找目标字符串的字符的下标的,也就是第stp+1个字符。
第三步:同时用一个v[x][y]数组表示节点[x,y]应该找的下一个字符在目标串中的下标
第四步:更新新的节点时遇到新节点[x,y]的v[x][y]<当前节点t的stp时就更新v[x][y]为t.stp,同时将该节点入队中。
代码:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
const int N=60;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct node{
int x,y,dis,stp;
}t;
int len;
int r,c;
int v[N][N];
PII ne[N][N][5];
char mp[N][N],s[10001];
int bfs()
{
queue<node> q;
q.push({1,1,0,0});
while(q.size())
{
auto t=q.front();
q.pop();
if(mp[t.x][t.y]==s[t.stp])
{
if(t.stp==len)
{
return t.dis+1;
}
t.stp++;
t.dis++;
v[t.x][t.y]=t.stp;
q.push(t);
continue;
}
for(int i=0;i<4;i++)
{
int x=ne[t.x][t.y][i].first;
int y=ne[t.x][t.y][i].second;
if(v[x][y]<t.stp)
{
v[x][y]=t.stp;
q.push({x,y,t.dis+1,t.stp});
}
}
}
return 0;
}
int main()
{
memset(v,-1,sizeof v);
scanf("%d%d",&r,&c);
for(int i=1;i<=r;i++)
scanf("%s",mp[i]+1);
scanf("%s",s);
len =strlen(s);
s[len]='*';
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
for(int k=0;k<4;k++)
{
int x=i+dx[k];
int y=j+dy[k];
while(mp[i][j]==mp[x][y])
x+=dx[k],y+=dy[k];
if(x<=0||x>r||y<=0||y>c)
{
ne[i][j][k]={i,j};
}else
{
ne[i][j][k]={x,y};
}
}
}
printf("%d",bfs());
return 0;
}