P7082: 小豫豫在开封
传统题
1.000s
时间限制
256MB
内存限制
1 提交
0 解决
【题目描述】
【题目描述】听闻开封被评为“河南省最适宜居住的城市之一”，小豫豫马不停蹄地赶往开封。
在逛公园时，小豫豫偶然遇到了一群可爱的大爷们，他们正在下一种名为“青春版国际象棋”的很新的国际象棋。
“青春版国际象棋”有无限大的棋盘，以及如下种类的棋子：
1、皇后（用字母 Q 表示）可以向八个方向（如图）移动任意步数。形式得讲，对于任意整数k≠0，皇后可以从 (a,b) 移动到 (a,b+k),(a+k,b),(a+k,b+k),(a+k,b-k)。
2、车(用字母 R 表示)可以向上下左右四个方向（如图）移动任意步数。形式得讲，对于任意整数 k≠0，棋子可以从 (a,b) 移动到 (a,b+k),(a+k,b)。
3、象(用字母 B 表示)可以斜向（如图）移动任意步数。形式得讲，对于任意整数 k≠0，棋子可以从 (a,b)移动到 (a+k,b+k),(a+k,b-k)。
4、骑士(用字母 N 表示)以 L 路线行走，如图。形式得讲，棋子可以从 (a,b) 移动到 (a+1,b+2), (a+1,b-2),(a+2,b+1),(a+2,b-1),(a-2,b-1),(a-2,b-1),(a-1,b+2),(a-1,b-2)。
5、国王(用字母K 表示)可以向八个方向（如图）移动1步。形式得讲，棋子可以从 (a,b) 移动到(a+1,b+1),(a+1,b),(a+1,b-1) , (a,b+1),(a,b-1) ,(a-1,b+1) ,(a-1,b) , (a-1,b-1)。
6、兵（用字母 P表示）只能向正上方走。形式得讲，棋子可以从(a,b)移动到 (a+1,b)。
小豫豫觉得很有趣，于是也参与了进来。
最开始，小豫豫拥有一颗超能力棋子，每回合小豫豫可以变身成为给定集合里的任一棋子，然后按照该棋子的方式移动一次。
现在有q次询问，每次给定一个可用的棋子类型集合以及四个整数 a, b, c,d ,小豫豫想知道，从(a,b)走到(c,d)的最小回合数是多少？
【输入格式】
一行一个整数 q，表示有 q 次询问。
对于每个询问：
一行一个字符串，表示给定的棋子类型集合。
一行四个整数 a, b, c, d表示从 (a,b)走到 (c,d)。
【输出格式】
对于每个询问：
每次一个整数，表示从 (a,b)到 (c,d)的最小回合数。
【样例输入1 】
2
NKP
3 3 5 1
NKP
2 6 5 3
【样例输出1】
2
2
【样例输入2】
2
B
2 8 3 6
B
2 8 5 5
【样例输出2】
-1
1
【样例解释】
对于第一组样例：
第一组询问：
可选的三种最小回合方案为:
1、变成兵走到 (4,3)，然后变成骑士走到(5,1) 。
2、变成骑士走到 (5,2)，然后变成国王走到 (5,1)。
3、变成国王走到 (4,2)，然后再次变成国王走到 (5,1)。
第二组询问从 (2,6)走到(5,3)：
方案为：变成骑士先走到 (4,5)或者 (3,4)，再变成骑士走到 (5,3)。
【数据范围】
对于 10%的数据，没有 N 字符，且保证存在 Q 字符
对于另外 10%的数据，保证同时存在 Q和 N字符
对于另外 10%的数据，没有 Q 字符，且保证存在 R字符
对于另外 10%的数据，保证字符串必然为"B "，即集合中只存在字符 B
对于另外 5%的数据，没有 Q和 R字符，且保证存在 B字符
对于另外 30%的数据，保证字符串必然为"N "，即集合中只存在字符 N
对于另外 10%的数据，没有 Q,R,B字符，且保证存在 N字符
对于另外 10%的数据，没有 Q,R,B,N字符，且保证存在 K字符
对于另外 5%的数据，保证字符串必然为" P"，即集合中只存在字符 P
对于所有的数据，保证 1≤q≤1000,-100000000≤a,b,c,d≤100000000