bfs优化技巧——键盘输入

Source

传送门:1104. 键盘输入 - AcWing题库

代码在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;
}