题目

有人做那道题吗？有的话谁能给出能获得超过 $10^6$ 分数的解法吗？我最终只做出了 $959971$ 分的【随机化+dp】做法，谁能教教这个萌新？

我的代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,m,u,v,dp[1009][15][15],f[1009][15][15],g[1009][15][15],l,d,e,b,ans,res[8009],_t,_l=2;
string c[19],T[209],t[209],w,perm[8009][1009];
char r[1009];
vector<pii> a[129];
stack<pii> p;
unordered_set<string> s;
mt19937 myrnd;
inline void cp(string *__T=T,string *__t=t){for(int i=0;i<m;++i) __t[i]=__T[i];}
inline void func(int _T){
	l=0,s.clear(),memset(dp,0x3f,sizeof(dp)),dp[0][u][v]=0,ans=INT_MAX,w="    "+c[u][v],cp(t,perm[_T]);
	for(int i=0;i<m;++i) if(s.find(t[i])==s.end()) for(int j=0;j<5;++j) r[++l]=t[i][j],w[0]=w[1],w[1]=w[2],w[2]=w[3],w[3]=w[4],w[4]=t[i][j],w[0]!=' '&&(s.insert(w),0);
	for(int i=1;i<=l;++i) for(pii &x:a[r[i]]) for(pii &y:a[r[i-1]]){
		int e=abs(x.first-y.first)+abs(x.second-y.second)+1+dp[i-1][y.first][y.second];
		if(e<dp[i][x.first][x.second]) dp[i][x.first][x.second]=e,f[i][x.first][x.second]=y.first,g[i][x.first][x.second]=y.second;
	}
	for(pii &x:a[r[l]]) if(dp[l][x.first][x.second]<ans) ans=dp[l][x.first][x.second],d=x.first,e=x.second;
	res[_T]=ans;
}
int main(){
	cin>>n>>m>>u>>v,a[0].push_back((pii){u,v}),myrnd.seed(time(0));
	for(int i=0;i<n;++i) cin>>c[i];
	for(int i=0;i<n;++i) for(int j=0;j<n;++j) a[c[i][j]].push_back((pii){i,j});
	for(int i=0;i<m;++i) cin>>T[i];
	cp(),func(0);
	cp(),reverse(t,t+m),func(1);
	while(clock()<CLOCKS_PER_SEC*1.8&&_l<8000) cp(),shuffle(t,t+m,myrnd),func(_l),++_l;
	_t=min_element(res,res+_l)-res;
	cp(perm[_t]),func(_t);
	for(int i=l;i;--i) p.push((pii){d,e}),b=d,d=f[i][b][e],e=g[i][b][e];
	for(int i=1;i<=l;++i) cout<<p.top().first<<" "<<p.top().second<<"\n",p.pop();
	return 0;
}