问题标题: 酷町堂：6190 TLE 求优化算法

先简述思路 录入n,m后预处理每一个点下一个方向点的坐标 再BFS 加入如果当前点匹配少就无法入队的剪枝

CODE:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
int n,m;
char a[60][60],s[10001];
int len,b[60][10001];
struct point{
	int x,y;
}next[60][60][4];
struct NODE{
	int x,y,t,step;
};
queue <NODE> q;
void init() {
	len=1;
	while(s[len]!=0){
		len++;
	}
	s[len]='*';
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c=a[i][j];
			for(int k=i+1;k<=n;k++)
				if(a[k][j]!=c){
					next[i][j][0].x=k;
					next[i][j][0].y=j;
					break;
				}
			for(int k=i-1;k>0;k--)
				if(a[k][j]!=c){
					next[i][j][1].x=k;
					next[i][j][1].y=j;
					break;
				}
			for(int k=j+1;k<=m;k++)
				if(a[i][k]!=c){
					next[i][j][2].x=i;
					next[i][j][2].y=k;
					break;
				}
			for(int k=j-1;k>0;k--)
				if(a[i][k]!=c){
					next[i][j][3].x=i;
					next[i][j][3].y=k;
					break;
				}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",a[i]+1);
	}
	scanf("%s",s+1);
	init();
	q.push(NODE{1,1,0,0});
	int nx,ny;
	memset(b,0xff,sizeof(b));
	while(!q.empty()){
		NODE h=q.front();
		q.pop();
		if(a[h.x][h.y]==s[h.t+1]){
			if(h.t+1==len){
				printf("%d\n",h.step+1);
				break;
			}
			q.push(NODE{h.x,h.y,h.t+1,h.step+1});
		}
		else {
			for(int i=0;i<4;i++){
				nx=next[h.x][h.y][i].x;
				ny=next[h.x][h.y][i].y;
				if(nx!=0 && ny!=0 && b[nx][ny]<h.t){
					b[nx][ny]=h.t;
					q.push(NODE{nx,ny,h.t,h.step+1});
				}
			}
		}
	}
	return 0;
}

能否在此算法基础上加以优化？

若无法继续优化 能否提供一种新的算法？

张曈在2021-02-18 17:48:13追加了内容

提交结果第1、2、5、7、10五个点TLE，73分