NC219033. 有始有终

描述

输入描述

第一行一个数字 ，代表接下来测试数据的组数
对于每个测试数据，第一行有两个数字 ，表示著矩阵的大小，每行有  个数字，共  行 。
第二行有两个数字 ，代表起点座标。
第三行有两个数字 ，代表终点座标。
第四行有一个数字 ，代表能往相邻且高度差不大于  的矩阵格行走。
最后的  行，每行有  个用空白隔开的整数，为每个矩阵格的高度，且介于  到  之间(包含  和 )。
请注意，地图的左上角座标为，而右下角为。

输出描述

对于每组测试数据，输出一个非负整数代表使用技能的次数

示例1

输入:

2
9 9
1 1
5 5
3
9 9 9 9 9 9 9 9 9
1 1 1 1 1 1 1 1 9
9 9 9 9 9 9 9 1 9
9 1 1 1 1 1 9 1 9
9 1 9 9 9 1 9 1 9
9 1 9 1 1 1 9 1 9
9 1 9 9 9 9 9 1 9
9 1 1 1 1 1 1 1 9
9 9 9 9 9 9 9 9 9
21 14
17 12
14 11
0
7 85 12 80 90 45 78 13 57 39 61 81 32 62 49 32 45 72 65 41 39
33 37 53 31 4 24 95 53 66 32 70 30 76 49 65 68 83 15 83 47 19
83 0 67 74 15 62 42 79 85 15 51 65 53 14 90 62 37 7 42 22 7
45 1 62 5 38 84 73 0 73 50 84 41 12 13 33 79 87 86 38 59 61
72 38 24 11 72 1 56 1 11 8 50 34 57 52 80 71 17 23 72 88 77
82 9 93 70 73 57 18 27 52 60 26 47 23 56 21 16 85 87 85 63 64
12 45 77 84 25 43 35 69 17 40 69 86 57 29 55 43 53 88 0 33 64
15 78 28 91 52 91 66 42 10 47 39 60 23 5 7 42 59 82 91 33 0
68 6 35 81 7 80 42 16 78 53 79 3 15 94 74 15 48 16 91 8 65
35 41 8 74 54 41 94 71 65 65 8 81 12 13 68 94 30 1 3 12 88
80 31 58 3 45 15 23 71 80 89 95 93 28 39 3 72 63 61 41 63 57
73 52 14 32 92 5 30 2 56 34 18 77 75 22 84 76 91 24 47 83 66
17 30 61 93 88 4 51 95 1 94 48 75 86 86 67 1 3 89 85 88 56
11 12 14 11 57 14 92 60 16 74 14 61 45 52 81 82 52 79 45 53 4

输出:

0
2

原站题解

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

struct node
{
	int x,y,h;
	bool operator<(const node &a)const
	{
		return a.h<h;
	}
}f;
priority_queue<node>Q;
int dx[]={1,-1,0,0,-1,-1,1,1,2,-2,0,0},dy[]={0,0,1,-1,1,-1,1,-1,0,0,2,-2};
bool V[35][35][75];
int main()
{
	int i,j,n,m,sx,sy,ex,ey,nx,ny,nh,a[35][35],D,T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d%d%d%d%d",&m,&n,&sy,&sx,&ey,&ex,&D);
		sy--,sx--,ey--,ex--;
		memset(V,0,sizeof(V));
		while(!Q.empty())Q.pop();
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)scanf("%d",&a[i][j]);
		V[sx][sy][0]=1,Q.push({sx,sy,0});
		while(!Q.empty()){
			f=Q.top(),Q.pop();
			if(f.x==ex&&f.y==ey)break;
			for(i=0;i<12;i++){
				nx=f.x+dx[i],ny=f.y+dy[i],nh=f.h;
				if(nx<0||nx>=n||ny<0||ny>=m)continue;
				if(i<4&&abs(a[f.x][f.y]-a[nx][ny])>D)nh++;
				if(i>=4)nh++;
				if(!V[nx][ny][nh])V[nx][ny][nh]=1,Q.push({nx,ny,nh});
			}
		}
		printf("%d\n",f.h);
	}
	return 0;
}