方格跳跃

第一行三个整数 H,W,d，表示网格图的长度与宽度，d 的含义如题面所示。
接下来 W 行，每行 H 个整数表示网格图中每个格子的数。

下一行是一个整数 Q(1≤ Q≤10⁵)，表示询问组数。
接下来 Q 行，每行两个整数 L 和 R 代表一组询问。
保证数据合法，即不存在无法从 L 按题意跳若干步跳到 R 的数据。

C++ 解法, 执行用时: 45ms, 内存消耗: 1168K, 提交时间: 2022-06-04 14:52:24

#include<bits/stdc++.h>
const int N=5e6+5;
int h,w,d,x[N],y[N],a,q,l,r;
long long s[N];
int main()
{
	scanf("%d%d%d",&h,&w,&d);
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
			scanf("%d",&a),x[a]=i,y[a]=j;
	for(int i=1;i<=h*w;i++)
		if(i>d)
			s[i]=s[i-d]+abs(x[i-d]-x[i])+abs(y[i-d]-y[i]);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d%d",&l,&r);
		printf("%lld\n",s[r]-s[l]);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 46ms, 内存消耗: 1144K, 提交时间: 2019-11-22 10:29:26

#include<bits/stdc++.h>
using namespace std;

int l,r,T,H,W,d,S[4000005],w[4000005],h[4000005];
int main()
{
	int i,j,k;
	scanf("%d%d%d",&H,&W,&d);
	for(i=1;i<=H;i++)
		for(j=1;j<=W;j++)scanf("%d",&k),h[k]=i,w[k]=j;
	for(i=d+1;i<=W*H;i++)S[i]=S[i-d]+abs(w[i]-w[i-d])+abs(h[i]-h[i-d]);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",S[r]-S[l]);
	}
	return 0;
}

详情