C++(g++ 7.5.0) 解法, 执行用时: 668ms, 内存消耗: 632K, 提交时间: 2022-09-23 21:30:57

#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);
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        cin>>mp[i][j];
    cin>>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};
            }
        }
    }
    cout<<bfs();


    return 0;
}

C++ 解法, 执行用时: 1151ms, 内存消耗: 25040K, 提交时间: 2022-04-02 22:22:09

#include<bits/stdc++.h>
using namespace std;
const int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};
struct node{
	int x,y,step,index;
}t;
int r,c,Next[51][51][4][2];
bool v[51][51][10001];
char s[10002],key[51][51];
queue <node> q;
int main(){
	cin>>r>>c;
	int len,x,y,i,j,k;
	for (i = 0;i < r;i++)
		cin>>key[i];
	cin>>s;
	len = strlen(s);
	s[len] = '*';
	for (i = 0;i < r;i++)
		for (j = 0;j < c;j++)
			for (k = 0;k < 4;k++){
				x = i;
				y = j;
				while (key[x][y] == key[i][j]){
					x += dx[k];
					y += dy[k];
				}
				Next[i][j][k][0] = x;
				Next[i][j][k][1] = y;
			}
	t.x = 0;
	t.y = 0;
	t.step = 0;
	t.index = 0;
	q.push(t);
	v[0][0][0] = 1;
	while (!q.empty()){
		t = q.front();
		q.pop();
		if (key[t.x][t.y] == s[t.index]){
			if (t.index == len)break;
			t.step++;
			t.index++;
			q.push(t);
			v[t.x][t.y][t.index] = 1;
			continue;
		}
		for (i = 0;i < 4;i++){
			x = Next[t.x][t.y][i][0];
			y = Next[t.x][t.y][i][1];
			if (0 <= x && x < r && 0 <= y && y < c && !v[x][y][t.index]){
				q.push((node){x,y,t.step + 1,t.index}) ;
				v[x][y][t.index] = 1;
			}
		}
	}
	cout<<t.step + 1;
	return 0;
}