P9322 [EGOI 2022] Superpiece / 超级棋子

思路

显然难点在于骑士。
较近的几个点步数可以由枚举得到。
我们考虑转移方法。
一个点可以向所有与它距离为 $2$ 的点用两步扩展，也可以向与它横纵坐标距离均为 $1$ 的点用两步扩展。
结合初始几个点所需的步数，易得最终大概是这样的（搬一张以前题解的图）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 0  3  2  3  2  3  4  5  4  5  6  7  6  7  8  9  8  9 10
 3  2  1  2  3  4  3  4  5  6  5  6  7  8  7  8  9 10  9
 2  1  4  3  2  3  4  5  4  5  6  7  6  7  8  9  8  9 10
 3  2  3  2  3  4  3  4  5  6  5  6  7  8  7  8  9 10  9
 2  3  2  3  4  3  4  5  4  5  6  7  6  7  8  9  8  9 10
 3  4  3  4  3  4  5  4  5  6  5  6  7  8  7  8  9 10  9
 4  3  4  3  4  5  4  5  6  5  6  7  6  7  8  9  8  9 10
 5  4  5  4  5  4  5  6  5  6  7  6  7  8  7  8  9 10  9
 4  5  4  5  4  5  6  5  6  7  6  7  8  7  8  9  8  9 10
 5  6  5  6  5  6  5  6  7  6  7  8  7  8  9  8  9 10  9
 6  5  6  5  6  5  6  7  6  7  8  7  8  9  8  9 10  9 10
 7  6  7  6  7  6  7  6  7  8  7  8  9  8  9 10  9 10 11
 6  7  6  7  6  7  6  7  8  7  8  9  8  9 10  9 10 11 10
 7  8  7  8  7  8  7  8  7  8  9  8  9 10  9 10 11 10 11
 8  7  8  7  8  7  8  7  8  9  8  9 10  9 10 11 10 11 12
 9  8  9  8  9  8  9  8  9  8  9 10  9 10 11 10 11 12 11
 8  9  8  9  8  9  8  9  8  9 10  9 10 11 10 11 12 11 12
 9 10  9 10  9 10  9 10  9 10  9 10 11 10 11 12 11 12 13
10  9 10  9 10  9 10  9 10  9 10 11 10 11 12 11 12 13 12
11 10 11 10 11 10 11 10 11 10 11 10 11 12 11 12 13 12 13
10 11 10 11 10 11 10 11 10 11 10 11 12 11 12 13 12 13 14
11 12 11 12 11 12 11 12 11 12 11 12 11 12 13 12 13 14 13

推出式子是 $t=\max{\frac{x}{2},\frac{y}{2},\frac{x+y}{3}}$，返回 $x+y-t+(x+y-t)\bmod 2$，离得最近的几个点特殊，特判即可。

后面的就好做了。
先判断无解情况：

  • 只有兵且 $a>c$ 或 $b\ne d$，此时无论如何都走不到终点。
  • 只有主教且终点与起点在不同颜色的格子上，主教的移动无法改变自身格子颜色，故无解。

再判断走一步就能到达的情况：

  • 皇后：同时包含城堡和主教的情况，见下。
  • 城堡：一次直线走可到达，即 $a=c$ 或 $b=d$。
  • 主教：一次斜线走可到达，即 $|a-c|=|b-d|$。
  • 骑士：前面讲了。
  • 国王：两个点的切比雪夫距离小于等于 $1$，即 $|a-c|\le 1$ 且 $|b-d|\le 1$。
  • 兵：向前走一步可到达，即 $a+1=c$ 且 $b=d$。

然后判断走两步可到达的情况：

  • 皇后一定可到达，只需先走到 $(a,d)$ 再走到 $(b,d)$ 即可。
  • 城堡与皇后同理。
  • 主教可在两步之内到达相同颜色的点，先走到两个点分别画一条斜率等于 $1$ 或 $-1$ 的直线的交点，再走到 $(c,d)$ 即可。
  • 骑士：前面讲了。
  • 国王：两个点的切比雪夫距离小于等于 $2$，即 $|a-c|\le 2$ 且 $|b-d|\le 2$。
  • 兵：向前走两步可到达，即 $a+2=c$ 且 $b=d$。

此后便不会再出现皇后和城堡了。
那么此时可能的两步走法是棋子的组合，枚举棋子 $A$ 一次能走到的点，再看棋子 $B$ 是否能一次走到即可（我们默认主教被放在棋子 $B$）。
此时若全不符合并且存在主教，则用任意的另外棋子到达颜色不相同的格子，再用主教走两步一定可到达，共三步。
最后处理最后三种棋子。

  • 骑士：前面讲了。
  • 国王：若只有国王，直接输出切比雪夫距离，若同时有国王和兵，等同于只有国王。
  • 兵：若只有兵，直接输出 $c-a$，若同时有国王和兵，等同于只有国王。

此时一定只剩下国王加骑士或兵加骑士。
发现所有国王和兵两步以上才能到达的点，骑士一定可以只用更小的步数到达。
枚举所有国王或兵两步能够到达的点，再加上骑士所需的步数，取最小值即为答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include<bits/stdc++.h>
#define fir first
#define sec second 
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
int T,t,a,b,c,d;
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int inf=2e18;
string s;
unordered_map<char,int>v;
int ndx[10]={1,1,2,2,-1,-1,-2,-2};
int ndy[10]={2,-2,1,-1,2,-2,1,-1};
int kdx[10]={0,0,1,1,1,-1,-1,-1};
int kdy[10]={1,-1,0,1,-1,0,1,-1};
int pdx[10]={1};
int pdy[10]={0};
int knight(int x,int y){
	if((x==0&&y==1)||(x==1&&y==0))return 3;
	if(x==2&&y==2)return 4;
	int t=max({(x+1)/2,(y+1)/2,(x+y+2)/3});
	if((x+y-t)%2==0)return t;return t+1;
}
signed main(){
//	freopen("chess.in","r",stdin); 
//	freopen("chess.out","w",stdout); 
	read(T);
	for(t=1;t<=T;t++){
		cin>>s;v.clear();
		fep(i,0,s.size())v[s[i]]=1;
		read(a,b,c,d);
		if(s.size()==1){
			if(v['B']==1){
				if(abs(a+b)%2!=abs(c+d)%2){
					puts("-1");
					continue;
				}
			}
			if(v['P']==1){
				if(b!=d||a>c){
					puts("-1");
					continue;
				}
			}
		}
		if(v['Q']==1){
			if(a==c||b==d||abs(a-c)==abs(b-d)||(abs(a-c)<=1&&abs(b-d)<=1)){
				puts("1");
				continue;
			}
		}
		if(v['R']==1){
			if(a==c||b==d){
				puts("1");
				continue;
			}
		}
		if(v['B']==1){
			if(abs(a-c)==abs(b-d)){
				puts("1");
				continue;
			}
		}
		if(v['N']==1){
			if(abs(a-c)==2&&abs(b-d)==1){
				puts("1");
				continue;
			}
			if(abs(a-c)==1&&abs(b-d)==2){
				puts("1");
				continue;
			}
		}
		if(v['K']==1){
			if(abs(a-c)<=1&&abs(b-d)<=1){
				puts("1");
				continue;
			}
		}
		if(v['P']==1){
			if(b==d&&a==c-1){
				puts("1");
				continue;
			}
		}
		if(v['Q']==1||v['R']==1){
			puts("2");
			continue;
		}
		if(v['B']==1&&abs(a-c)%2==abs(b-d)%2){
			puts("2");
			continue;
		}
		if(v['N']==1&&v['B']==1){
			int flg=0;
			rep(i,0,7){
				int na=a+ndx[i];
				int nb=b+ndy[i];
				if(abs(na-c)==abs(nb-d)){
					puts("2");
					flg=1;break;
				}
			}
			if(flg)continue;
		}
		if(v['P']==1){
			if(a+2==c&&b==d){
				puts("2");
				continue;
			}
		}
		if(v['K']==1){
			if(abs(a-c)<=2&&abs(b-d)<=2){
				puts("2");
				continue;
			}
		}
		if(v['N']==1){
			if(knight(abs(a-c),abs(b-d))==2){
				puts("2");
				continue;
			}
		}
		if(v['P']==1&&v['N']==1){
			if(knight(abs(a+1-c),abs(b-d))==1){
				puts("2");
				continue;
			}
		}
		if(v['K']==1&&v['N']==1){
			int flg=0;
			rep(i,-1,1){
				rep(j,-1,1){
					if(knight(abs(a+i-c),abs(b+j-c))==1){
						flg=1;break;
					}
				}
			}
			if(flg){
				puts("2");
				continue;
			}
		}
		if(v['B']==1){
			puts("3");
			continue;
		}
		if(s.size()==1){
			if(v['P']==1){
				print(c-a);
				puts("");
				continue;
			}
			if(v['K']==1){
				print(max(abs(a-c),abs(b-d)));
				puts("");continue;
			}
			if(v['N']==1){
				print(knight(abs(a-c),abs(b-d)));
				puts("");
				continue;
			}
		}
		if(s.size()==2){
			if(v['P']==1&&v['K']==1){
				print(max(abs(a-c),abs(b-d)));
				puts("");continue;
			}
			if(v['P']==1&&v['N']==1){
				int ans=min(knight(abs(a-c),abs(b-d)),knight(abs(a+1-c),abs(b-d))+1);
				print(ans);puts("");continue;
			}
		}
		int ans=knight(abs(a-c),abs(b-d));
		rep(i,-1,1){
			rep(j,-1,1){
				int na=a+i;
				int nb=b+j;
				ans=min(ans,knight(abs(na-c),abs(nb-d))+1);
			}
		}
		rep(i,-2,2){
			rep(j,-2,2){
				int na=a+i;
				int nb=b+j;
				ans=min(ans,knight(abs(na-c),abs(nb-d))+2);
			}
		}
		print(ans);puts("");
	}
}