弹指间计算机协会 X Five Pines Robomaster实验室 考核题面与题解

大一组

绩点

Description

阿杰在大一学习了C++入门课程，这门课程的总绩点计算方法为：

总绩点=作业分数× 20% +小测分数× 30% +期末考试分数× 50%

阿杰想知道，这门课程的最终绩点。

Input

输入只有1行，包含三个非负整数A、B、C，分别表示阿杰的作业成绩、小测

分数和期末考试分数。相邻两个数之间用一个空格隔开，三项分数满分都是100分。

Output

输出只有1行，包含一个整数，即阿杰这门课程的总绩点，满分也是100分。

Sample Input 1

100 100 80
1

Sample Output 1

90
1

Sample Input 2

60 90 80
1

Sample Output 2

79
1

代码

#include
using namespace std;
int a,b,c;
int main(){
	cin>>a>>b>>c;
 	int res=0.2*a+0.3*b+0.5*c;
   cout<<res<<endl;
  return 0;
}
1
2
3
4
5
6
7
8
9

字符串统计

Description

给定一个字符串，要求统计字符串的字符

注意：字符串中可能包含大、小写英文字母、数字字符、空格和换行符。统计字符串字符数时，空格和换行符不计算在内。

Input

输入只有一行，一个字符串s。

Output

输出只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。

Sample Input 1

234
1

Sample Output 1

3
1

Sample Input 2

Ca 45
1

Sample Output 2

4
1

Hint

【输入输出样例2说明】

字符串中共有5个字符，包括1个大写英文字母，

1个小写英文字母和2个数字字符，

还有1个空格。由于空格不计入结果中，故标题的有效字符数为4个。

【数据规模与约定】

规定|s|表示字符串s的长度（即字符串中的字符和空格数）。

对于40%的数据，1 ≤ |s| ≤ 5，保证输入为数字字符及行末换行符。

对于80%的数据，1 ≤ |s| ≤ 5，输入只可能包含大、小写英文字母、数字字符及行末换行符。

对于100%的数据，1 ≤ |s| ≤ 5，输入可能包含大、小写英文字母、数字字符、空格和行末换行符。

代码

#include
#include
using namespace std;
int main(){
	string s;
    getline(cin,s);
  	int res=0;
    for(int i=0;i<s.size();i++)
      if (s[i]!=' '&&s[i]!='\n')
      	res++;
    cout<<res;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

报销

Description

Min找老师报销费用。第一天，Min给老师一张发票；

之后两天（第二天和第三天），每天给老师两张发票；

之后三天（第四、五、六天），每天给老师三张发票；

之后四天（第七、八、九、十天），每天给老师四张发票……；

这种报销模式会一直这样延续下去：当连续N天每天收到N张发票后，老师会在之后的连续N+1天里，每天收到N+1张发票。

请计算在前K天里，老师一共获得了多少发票。

Input

输入只有1行，包含一个正整数K，表示上交发票的天数。

Output

输出只有1行，包含一个正整数，即老师收到的发票数。

Sample Input 1

5
1

Sample Output 1

11
1

Sample Input 2

1000
1

Sample Output 2

29820
1

Hint

【输入输出样例1说明】

老师第一天收到一张发票；第二天和第三天，每天收到两张发票；第四、五天，

每天收到三张发票。因此一共收到1+2+2+3+3=11张发票。

【数据说明】

对于100%的数据，1≤K≤10,000。

代码

#include
using namespace std;
int n;
long long res=0;
int main(){
	cin>>n;
    int j=0,k=0;
    for(int i=1;i<=10000&&i<=n;i++)
    	for(int j=0;j<i&&k<n;j++,k++)
        	res+=i;
  cout<<res;
}
1
2
3
4
5
6
7
8
9
10
11
12

质因数分解

Description

已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。

Input

输入只有一行，包含一个正整数n。

Output

输出只有一行，包含一个正整数p，即较大的那个质数。

Sample Input 1

21
1

Sample Output 1

7
1

Hint

对于60%的数据，6 ≤ n ≤ 1000。

对于100%的数据，6 ≤ n ≤ $2\times {10}^9$

代码

#include
using namespace std;
int main(){
	long long n;
	cin>>n;
	for(long long i=2;i*i<=n;i++){
		if (n%i==0){
			cout<<n/i;
			return 0;
		}
	}
} 
1
2
3
4
5
6
7
8
9
10
11
12

骨牌（此题已砍）

Description

在一个有$2\ast n$个格子的大长方形槽内放置$1\ast 2$的小骨牌，骨牌可以横放可以竖放，有多少种不同的放置方式可以将大长方形槽填满？

例如，当$n=3$时，一共有3种方式。

Input

输入只有一行，包含一个正整数n。

Output

输出只有一行，包含一个正整数res，即结果

Sample Input 1

3
1

Sample Output 1

3
1

Hint

对于100%的数据，1 ≤ n ≤ 50

题解

当$n=1$,有且只有一种摆法

当$n=2$,可以两个横放，也可以两个竖放，有二种摆法

当$n=3$,可以由$n=2$的情况再竖放一个骨牌得到，也可以由$n=1$的情况再横放两个骨牌得到（不能竖放两个骨牌，会与$n=2$的情况重复）。

以此类推，$f_n=f_{n-1}+f_{n-2}$

代码

#include
using namespace std;
long long f[55];
int main(){
	f[1]=1;
	f[2]=2;
	int n;
	cin>>n;
	for(int i=3;i<=n;i++)
		f[i]=f[i-1]+f[i-2];
	cout<<f[n];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

复数

Description

给定两个复数 $a+bi$ 与 $c+di$ ，求他们相加，相减，相乘后的结果

注意，本题要求必须使用class(类)来完成复数的定义

Input

输入共一行，为4个整数，从左至右分别为a,b,c,d，用空格隔开，代表两个复数a+bi, c+di

Output

输出共三行，从上到下分别为$a+bi$ 与 $c+di$的和，差，积

输出形式为“ $m\pm ni$”，如 $3+4i,6-9i,-2-7i,-1+1i$

特别地，当实部为0时，只输出虚部，如 $4i,-1i$；

当虚部为0时，只输出实部，如 $-5,1$ ；

当实部虚部均为0时，输出 $0$

Sample Input 1

1 2 3 4
1

Sample Output 1

4+6i
-2-2i
-5+10i
1
2
3

Sample Input 2

1 0 1 1
1

Sample Output 2

2+1i
-1i
1+1i
1
2
3

Hint

数据范围：

对于100%的测试用例，$-10000<a,b,c,d<10000$其中 $a,b,c,d\in Z$

代码

#include
#include
using namespace std;
class Complex {
public:
    int m, n;
    Complex operator+(Complex& c2) {
        Complex res;
        res.m = m + c2.m;
        res.n = n + c2.n;
        return res;
    }
    Complex operator-(Complex& c2) {
        Complex res;
        res.m = m - c2.m;
        res.n = n - c2.n;
        return res;
    }
    Complex operator*(Complex& c2) {
        Complex res;
        res.m = m * c2.m - n * c2.n;
        res.n = n * c2.m + m * c2.n;
        return res;
    }
    void cprint() {
        if (m == 0 && n == 0)
            printf("0\n");
        else if (m == 0 && n != 0)
            printf("%di\n", n);
        else if (m != 0 && n == 0)
            printf("%d\n", m);
        else printf("%d%+di\n", m, n);
    }

};

int main() {
    Complex c1, c2;
    cin >> c1.m >> c1.n >> c2.m >> c2.n;
    Complex c3 = c1 + c2;
    c3.cprint();
    c3 = c1 - c2;
    c3.cprint();
    c3 = c1 * c2;
    c3.cprint();
    return 0;
}
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

大二组

韭菜

Description

在今后的几天内Jerry将学习美元与人民币的汇率。编写程序帮助Jerry何时应买或卖人民币或美元，使他从100美元开始，最后能获得最高可能的价值。

Input

第一行是一个自然数N，1≤N≤100，表示Jerry学习汇率的天数。

接下来的N行中每行是一个自然数A，1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，Jerry既能用100美元买A人民币也能用A人民币购买100美元。

Output

第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。

注意：Jerry必须在最后一天结束之前将他的钱都换成美元。

Sample Input 1

5
400
300
500
300
250
1
2
3
4
5
6

Sample Output 1

266.67
1

Hint

样例解释

Day 1 … changing 100.0000美元= 400.0000人民币

Day 2 … changing 400.0000人民币= 133.3333美元

Day 3 … changing 133.3333美元= 666.6666人民币

Day 5 … changing 666.6666人民币= 266.6666美元

题解

状态机dp

钱有两种状态：美元，记为0状态。RMB，记为1状态。记$f_{i,0}$表示最优策略下第$i$天的美元数量，$f_{i,1}$表示最优策略下第$i$天的人民币数量。

设第$i$天汇率汇率为$a_i$，在最优策略下：当第$i-1$天汇率>第$i$天，可以把人民币兑换成美元$f_{i,0}=f_{i-1,1}/a_i$。当第$i-1$天汇率<第$i$天，可以把美元兑换为人民币$f_{i,1}=f_{i-1,0}\ast a_i$。

把$i$的维度优化掉，得到最终递推关系:
{ f 0 = f 1 / a i a i − 1 > a i f 1 = f 0 ∗ a i a i − 1 < a i {f0=f1/aiai−1>aif1=f0∗aiai−1<ai

{f0​=f1​/ai​f1​=f0​∗ai​​ai−1​>ai​ai−1​<ai​​
在最后一天，一定会把所有的钱都换成美元，则值为$f_0$或$f_1/a_n$

代码

#include
using namespace std;
double f[2];//0为美元，1为rmb 
double a[1005];
double st=1;
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]=a[i]/100.0;
	}
	f[0]=100;
	f[1]=100*a[1];
	for(int i=2;i<=n;i++){
		if (a[i-1]<a[i]){
			f[1]=f[0]*a[i];		
		}
		if (a[i-1]>a[i]){
			f[0]=f[1]/a[i];
		}
//		cout<<"day"<
	}
	double res=max(f[0],f[1]/a[n]);
	printf("%.2f",res);
	return 0;
}
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

闭合区域面积统计

Description

编程计算由‘*’号围成的下列图形的面积。面积的计算方法是统计*号所围成

的闭合曲线中水平线和垂直线交点的数目。如图所示，在10*10的二维数组中，

有*围住了15个点，因此面积为15。

Input

一个10*10的二维数组，里面的数为0和1,1代表着*号 。

Output

一个整数，代表被围住的点个数。

Sample Input 1

0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
1
2
3
4
5
6
7
8
9
10

Sample Output 1

15
1

题解

bfs，从左上角、右上角、左下角、右下角为起点找到外圈的0，再找出1的个数，则剩下的0的个数就是被1包围的0

代码

#include
#include
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int map[10][10];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int cnt0=0,cnt1=0;
int st[10][10];
void bfs0(){
	queue<PII> q;
  	if (map[0][0]==0)
		q.push({0,0});
    if (map[0][9]==0)
  		q.push({0,9});
    if (map[9][0]==0)
	  	q.push({9,0});
  	if (map[9][9]==0)  
  		q.push({9,9});
	while(!q.empty()){
		PII p=q.front();
		q.pop();
		st[p.x][p.y]=1;
		cnt0++;
//		cout<
		for(int k=0;k<4;k++){
			int newx=p.x+dx[k];
			int newy=p.y+dy[k];
			if (newx<0||newx>=10||newy<0||newy>=10)
				continue;
			if (st[newx][newy])
				continue;
			if (map[newx][newy]==1)
				continue;
			q.push({newx,newy});
			st[newx][newy]=1;
		}
	}
}
int main(){
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			cin>>map[i][j];
	bfs0();
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++){
			if (map[i][j]==1)
				cnt1++;
		}
//	cout<
	int res=100-cnt0-cnt1;
	cout<<res;
}
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

晒衣服

Description

熊大妈需要给宝宝们晒衣服。

衣服在自然条件下用 1 的时间可以晒干 A 点湿度。抠门的熊大妈买了 1 台烘衣机。使用烘衣机可以让你用单位 1 时间使 1件衣服除开自然晒干的 A 点湿度外，还可烘干 B 点湿度，但在单位 1 时间内只能对 1 件衣服使用。

N 件的衣服因为种种原因而不一样湿，现在告诉你每件衣服的湿度，要你求出弄干所有衣服的最少时间（湿度为 0 为干）。

Input

第一行N，A ，B ， 接下来N行 ，每行一个正整数 ，表示衣服的湿度（1<= 湿度,A,B<=500000,1<=N<=500000）。

Output

一个正整数，表示弄干衣服的最小时间

Sample Input 1

3 2 1
1
2
3
1
2
3
4

Sample Output 1

1
1

Hint

对于40%的测试用例，n <= 5000

对于70%的测试用例，n <= 10000

对于全部的测试用例，n <= 500000

【样例解析】

第 1 个时间内，用机器处理第 3 件衣服，此外，所有衣服自然晒干 2。花费 1 时间全部弄干。

题解

建大根堆，模拟。堆顶为（不考虑自然风干的情况下）湿度最大的衣服，（不考虑自然风干时）当前湿度记为$m$。记当前时间为$t$，当$m-t\ast a\le 0$时，表示衣服已经自然晒干。否则，对它用烘干机，$m\leftarrow m-b$,塞回堆内，计时。

代码

#include
#include
#include
using namespace std;
int main(){
	int n,a,b;
	cin>>n>>a>>b;
	priority_queue<int> q;
	for(int i=1;i<=n;i++){
		int shidu;
		cin>>shidu;
		q.push(shidu);
	}
	int t=0;
	do{
      	int p=q.top();
      	q.pop();
      	if (p-a*t<=0)
			break;
		t++;
		p-=b;
     	q.push(p);
	}while(1);
	cout<<t<<endl;
}
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

奶酪

Description

现有一块大奶酪，它的高度为 $h$，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中，奶酪的下表面为 $z=0$，奶酪的上表面为 $z=h$。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在不破坏奶酪的情况下，能否利用已有的空洞跑 到奶酪的上表面去?

空间内两点 $P_1(x_1,y_1,z_1)$、$P2(x_2,y_2,z_2)$ 的距离公式如下：

$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(P_1,P_2)=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2+(z_1-z_2{)}^2}$

Input

每个输入文件包含多组数据。

第一行，包含一个正整数 $T$，代表该输入文件中所含的数据组数。

接下来是 $T$T组数据，每组数据的格式如下： 第一行包含三个正整数 $n,h,r$，两个数之间以一个空格分开，分别代表奶酪中空洞的数量，奶酪的高度和空洞的半径。

接下来的 $n$行，每行包含三个整数 $x,y,z$，两个数之间以一个空格分开，表示空洞球心坐标为$ (x,y,z)$。

Output

$T$ 行，分别对应 $T$ 组数据的答案，如果在第 $i$ 组数据中，Jerry 能从下表面跑到上表面，则输出 Yes，如果不能，则输出 No。

Sample Input 1

3 
2 4 1 
0 0 1 
0 0 3 
2 5 1 
0 0 1 
0 0 4 
2 5 2 
0 0 2 
2 0 4
1
2
3
4
5
6
7
8
9
10

Sample Output 1

Yes
No
Yes
1
2
3

Hint

第一组数据,由奶酪的剖面图可见：

第一个空洞在 $(0,0,0)$ 与下表面相切；

第二个空洞在 $(0,0,4)$ 与上表面相切；

两个空洞在 $(0,0,2)$ 相切。

输出 Yes。

第二组数据,由奶酪的剖面图可见：

两个空洞既不相交也不相切。

输出 No。

第三组数据,由奶酪的剖面图可见：

两个空洞相交，且与上下表面相切或相交。

输出 Yes。

【数据规模与约定】

对于 $20\%$ 的数据，$n=1$，$1\le h$，$r\le 10^4$，坐标的绝对值不超过 $10^4$。

对于 $40\%$ 的数据，$1\le n\le 8$，$1\le h$，$r\le 10^4$，坐标的绝对值不超过 $10^4$。

对于 $80\%$ 的数据，$1\le n\le 10^3$，$1\le h$ , $r\le 10^4$，坐标的绝对值不超过 $10^4$。

对于 $100\%$ 的数据，$1\le n\le 1\times 10^3$，$1\le h$ , $r\le 10^9$，$T\le 20$，坐标的绝对值不超过 $10^9$。

题解

建图，设0号点为起点，$n+1$号点为终点。将每个洞视为图中的点。若洞高度绝对值小于半径$r$，则起点连到该点。若洞高度大于$h-r$,则该点连到终点。若距离小于半径的两倍，则两个洞所代表的点连一条边。建图完成后，dfs

代码

#include
#include
#include
#include
using namespace std;
typedef long long ll;
vector<int> G[1005];
double ball[1005][4];
bool st[1005];
void dfs(int i){
	st[i]=1;
	for(auto node:G[i]){
		if (!st[node])
			dfs(node);
	}
}
signed main(){
	freopen("res.in","r",stdin);
	freopen("res.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		memset(ball,0,sizeof ball);
		memset(st,0,sizeof st);
		int n;
		double h,r;
		cin>>n>>h>>r;
		for(int i=0;i<=n+1;i++)
			G[i].clear(); 
		for(int i=1;i<=n;i++){
			cin>>ball[i][1]>>ball[i][2]>>ball[i][3];
		}
		for(int i=1;i<=n;i++){
			if (ball[i][3]<=r){
				G[0].push_back(i);//0号点为起点，底边
			 	G[i].push_back(0);
			}
			if (ball[i][3]>=h-r){
				G[n+1].push_back(i);//n+1号点为终点 
				G[i].push_back(n+1);
			}
			for(int j=i+1;j<=n;j++){
				double sqrdst=(ball[i][1]-ball[j][1])*(ball[i][1]-ball[j][1])
						  +(ball[i][2]-ball[j][2])*(ball[i][2]-ball[j][2])
						  +(ball[i][3]-ball[j][3])*(ball[i][3]-ball[j][3]);
				if (sqrdst<=4*r*r){
					G[i].push_back(j);
					G[j].push_back(i);
				}
			}
		}
		dfs(0);
		if (st[n+1])
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
}
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

机器人搬重物

Description

机器人移动学会 RMI 现在正尝试用机器人搬运物品。机器人的形状是一个直径 $1.6$ 米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个 $N\times M$ 的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动 $1$ 步 Creep；向前移动$2$步 Walk；向前移动 $3$ 步 Run；向左转 Left；向右转 Right。每个指令所需要的时间为 $1$ 秒。请你计算一下机器人完成任务所需的最少时间。

Input

第一行为两个正整数$N,M(N,M\le 50)$，下面$N$行是储藏室的构造，$0$表示无障碍，$1$表示有障碍，数字之间用一个空格隔开。接着一行有$4$个整数和$1$个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

Output

一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出$-1$。

Sample Input 1

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S
1
2
3
4
5
6
7
8
9
10
11

Sample Output 1

12
1

题解

bfs。对于每个点，需要记录的是每一种朝向时所需的步数。某个点某朝向的步数第一次被更新时，一定是最优解。由于障碍物在格子里而机器人在格子交叉点里，所以需要判断机器人是否撞墙/撞障碍物。对于机器人位置$(x,y)$,则$(x-1,y-1),(x-1,y),(x,y-1),(x,y)$位置的障碍物都不能撞到。也不能撞墙，即需要满足$0<x<n,0<y<m$

代码

#include
#include
#include
#include
#include
using namespace std;
struct posd{
	int x, y, d;
};
int collidx[4] = { -1, 0,-1,0 };//障碍物
int collidy[4] = { -1,-1, 0,0 };
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int dist[55][55][4];//0 北 1南 2西 3东
map<char, int> c2i = {{'N',0},{'S',1},{'W',2},{'E',3}};
int ditu[55][55];
int n, m;
bool collide(int x, int y) {
	if (x == 0 || y == 0 || x >= n || y >= m)
		return true;
	for (int k = 0;k < 4;k++) {
		int tx = x + collidx[k];
		int ty = y + collidy[k];
		if (ditu[tx][ty] == 1)
			return true;
	}
	return false;
}
int main() {
	cin >> n >> m;
	for (int i = 0;i < n;i++)
		for (int j = 0;j < m;j++)
			cin >> ditu[i][j];
	int startx, starty, endx, endy;
	char startd;
	cin >> startx >> starty >> endx >> endy;
	cin >> startd;
	memset(dist, 0x3f3f3f3f, sizeof dist);
	queue<posd> q;
	q.push({ startx,starty,c2i[startd] });
	dist[startx][starty][c2i[startd]] = 0;
	while (!q.empty()) {
		auto p= q.front();
		q.pop();
		if (p.d == 0 || p.d == 1) {//从南北转到东西
			if (dist[p.x][p.y][2] == 0x3f3f3f3f) {
				dist[p.x][p.y][2] = dist[p.x][p.y][p.d] + 1;
				q.push({ p.x,p.y,2 });
			}
			if (dist[p.x][p.y][3] == 0x3f3f3f3f) {
				dist[p.x][p.y][3] = dist[p.x][p.y][p.d] + 1;
				q.push({ p.x,p.y,3 });
			}
		}
		if (p.d == 2 || p.d == 3) {//从东西转到南北
			if (dist[p.x][p.y][0] == 0x3f3f3f3f) {
				dist[p.x][p.y][0] = dist[p.x][p.y][p.d] + 1;
				q.push({ p.x,p.y,0 });
			}
			if (dist[p.x][p.y][1] == 0x3f3f3f3f) {
				dist[p.x][p.y][1] = dist[p.x][p.y][p.d] + 1;
				q.push({ p.x,p.y,1 });
			}
		}
		//往对应方向走1/2/3步
		int tx = p.x, ty = p.y;
		for (int _ = 0;_ <3;_++) {
			tx +=dx[p.d];
			ty +=dy[p.d];
			if (collide(tx, ty))
				break;
			if (dist[tx][ty][p.d] != 0x3f3f3f3f)
				continue;
			dist[tx][ty][p.d] = dist[p.x][p.y][p.d] + 1;
			q.push({ tx,ty,p.d });
		}
	}
	int res = 0x3f3f3f3f;
	for (int k = 0;k < 4;k++)
		res = min(res, dist[endx][endy][k]);
    if (res==0x3f3f3f3f)
      	cout<<-1;
    else 
		cout << res << endl;
}
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