正确性有待商榷 但是ac

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,K;
int f[N][N][7];
int a[N][N];
int xa,xb,ya,yb;
int mn[7][N];
int ans=0x3f3f3f3f;
int main(){
	scanf("%d",&n);
	scanf("%d",&m);
	scanf("%d",&K);
	scanf("%d",&xa);
	scanf("%d",&ya);
	scanf("%d",&xb);
	scanf("%d",&yb);
	memset(mn,0x3f,sizeof(mn));
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			f[i][j][0]=abs(xa-i)+abs(ya-j);
			mn[0][a[i][j]]=min(mn[0][a[i][j]],f[i][j][0]);
		}
	}
	for(int k=1;k<=K;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				f[i][j][k]=mn[k-1][a[i][j]];
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				f[i][j][k]=min(min(min(f[i][j+1][k]+1,f[i][j-1][k]+1),min(f[i-1][j][k]+1,f[i+1][j][k]+1)),f[i][j][k]);
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				mn[k][a[i][j]]=min(mn[k][a[i][j]],f[i][j][k]);
			}
		}
	}
	for(int i=0;i<=K;i++){
		ans=min(f[xb][yb][i],ans);
	}
	cout<<ans;
	return 0;
}

实际上就是求到每个点用了若干次传送阵的情况下的最小花费。 考虑开设 dp[1005][1005][6]，其中 dp[x][y][t] 表示到点(x, y) 使用 $t$ 次传送阵时的最小花费。

接下来考虑 BFS。 由于 BFS 的过程中要先将距离更近的点放入队列，所以先处理编号相同的传送阵。这可以提前用 vector 存起来。 我们发现同编号内的传送不需要反复传，只需要传一次，所以这里可以考虑打标记，传送过一次就打上标记，下次同编号就不再考虑传送问题。 之后正常处理四个方向的连通，并放入队列中。

最后在目标位置处求最小答案并输出即可。