发布于 

【FLYIOI63】逃离 题解

题目链接here

这是一道非常有思维难度和代码强度的宽搜好题。

题目大意

在一个地图中有两个人物和一些障碍物。

小z具有技能急速:每次移动可以走两步(允许这两步的方向不同,也允许不走第二步);

小m具有技能跳跃:若移动的方向为障碍且障碍后为空地,可借助障碍直接跳跃至空地。

计算两人相遇最少要花费多少秒。

如上图所示，黄色表示可以到达区域，黑色表示障碍物。

核心思路

通过数据范围可以发现此题的n≤1000n\leq 1000，就可以进行广搜，并且留下了可观的常数范围。

广搜小z

分解小z技能

小z的技能相当于在一秒内运用两次常规操作。因此我们只需要对小z做两次push即可。

小z的搜索代码

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
void bfs1(int xs,int ys) {
	int tx[5]={0,1,0,-1,0};
	int ty[5]={0,0,1,0,-1};
	queue<edge2> q;
	q.push((edge2){0,xs,ys});
	have[xs][ys]=1;
	z[xs][ys]=0;
	while(!q.empty()) {
		int x=q.front().xq,y=q.front().yq,s=q.front().s;
		q.pop();
		if(a[x][y]) continue;
		for(int i=1; i<=4; i++) {
			int xx=x+tx[i],yy=y+ty[i];

			if(xx<1||xx>n||yy<1||yy>n||a[xx][yy]) continue;
			if(!have[xx][yy]) {
				have[xx][yy]=1;
				z[xx][yy]=s+1;//答案存在z数组中
				q.push((edge2){s+1,xx,yy});//跳第一次到达的点
			}
			for(int j=1; j<=4; j++) {
				int xr=xx+tx[j],yr=yy+ty[j];
				if(xr<1||xr>n||yr<1||yr>n||a[xr][yr]||have[xr][yr]) continue;//如果中间的这个点是障碍物则无法运用技能
				have[xr][yr]=1;
				z[xr][yr]=s+1;//答案存在z数组中
				q.push((edge2){s+1,xr,yr});//运用技能调达的点
			}
		}
	}
}

广搜小m

分解小m技能

小m的技能相当于如果常规操作跳到一个障碍物上，那么可以在跳跃方向上继续向前跳一格，但是要判断前面的这一格是否为障碍物。

小z的搜索代码

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
void bfs1(int xs,int ys) {
	int tx[5]={0,1,0,-1,0};
	int ty[5]={0,0,1,0,-1};
	
	queue<edge> q;
	q.push((edge){xs,ys});
	while(!q.empty()) {
		int x=q.front().xq,y=q.front().yq;

		q.pop();
		for(int i=1; i<=4; i++) {
			int xx=x+tx[i],yy=y+ty[i];
			if(have[xx][yy]||xx<1||xx>n||yy<1||yy>n) continue;
			
			if(a[xx][yy]) {
				if(i==1) xx++;
				if(i==2) yy++;
				if(i==3) xx--;
				if(i==4) yy--;
			}//如果xx,yy是障碍物则跳过障碍物，针对不同的来路要跳到指定的地方
			
			if(have[xx][yy]||xx<1||xx>n||yy<1||yy>n) continue;
			
			if(!a[xx][yy]) {
				m[xx][yy]=min(m[xx][yy],m[x][y]+1);//答案存储在m数组中
				q.push((edge){xx,yy});
				have[xx][yy]=1;
			}
		}
		
	}
}

统计答案

Θ(nm)\Theta(nm)扫整个图一遍，找到max⁡(zi,j,mi,j)\max(z_{i,j},m_{i,j})最小的点。

1
2
3
4
for(int i=1; i<=n; i++)
	for(int j=1; j<=n; j++) {
		ans=min(ans,max(m[i][j],z[i][j]));
	}

完整代码

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
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000+10
#define INF 0x3f3f3f3f
int read() {
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,xa,xb,ya,yb;

int a[MAXN][MAXN];

int z[MAXN][MAXN],m[MAXN][MAXN];


void debug1() {
	cout<<endl;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			printf("%3d",m[i][j]==INF?0:m[i][j]);
		}
		cout<<endl;
	}
}


void debug2() {
	cout<<endl;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			printf("%3d",(z[i][j]==INF?0:z[i][j]));
		}
		cout<<endl;
	}
}

struct edge{
	int xq,yq;
};

int have[MAXN][MAXN];

void bfs1(int xs,int ys) {
	int tx[5]={0,1,0,-1,0};
	int ty[5]={0,0,1,0,-1};
	
	queue<edge> q;
	q.push((edge){xs,ys});
	while(!q.empty()) {
		int x=q.front().xq,y=q.front().yq;

		q.pop();
		for(int i=1; i<=4; i++) {
			int xx=x+tx[i],yy=y+ty[i];
			if(have[xx][yy]||xx<1||xx>n||yy<1||yy>n) continue;
			
			if(a[xx][yy]) {
				if(i==1) xx++;
				if(i==2) yy++;
				if(i==3) xx--;
				if(i==4) yy--;
			}
			
			if(have[xx][yy]||xx<1||xx>n||yy<1||yy>n) continue;
			
			if(!a[xx][yy]) {
				m[xx][yy]=min(m[xx][yy],m[x][y]+1);
				q.push((edge){xx,yy});
				have[xx][yy]=1;
			}
		}
		
	}
}

struct edge2{
	int s,xq,yq;
};

void bfs2(int xs,int ys) {
	int tx[5]={0,1,0,-1,0};
	int ty[5]={0,0,1,0,-1};
	queue<edge2> q;
	q.push((edge2){0,xs,ys});
	have[xs][ys]=1;
	z[xs][ys]=0;
	while(!q.empty()) {
		int x=q.front().xq,y=q.front().yq,s=q.front().s;
		q.pop();
		if(a[x][y]) continue;
		for(int i=1; i<=4; i++) {
			int xx=x+tx[i],yy=y+ty[i];

			if(xx<1||xx>n||yy<1||yy>n||a[xx][yy]) continue;
			if(!have[xx][yy]) {
				have[xx][yy]=1;
				z[xx][yy]=s+1;
				q.push((edge2){s+1,xx,yy});
			}
			for(int j=1; j<=4; j++) {
				int xr=xx+tx[j],yr=yy+ty[j];
				if(xr<1||xr>n||yr<1||yr>n||a[xr][yr]||have[xr][yr]) continue;
				have[xr][yr]=1;
				z[xr][yr]=s+1;
				q.push((edge2){s+1,xr,yr});
			}
		}
	}
}

int main() {
	n=read(),xa=read(),ya=read(),xb=read(),yb=read();
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) a[i][j]=getchar()-'0';
		getchar();
	}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) 
			m[i][j]=INF,z[i][j]=INF;
	m[xb][yb]=0;
	bfs1(xb,yb);
	
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) 
			have[i][j]=0;
	z[xa][ya]=0;
	bfs2(xa,ya);
	//debug1();
	//debug2();
	int ans=INF;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++) {
			ans=min(ans,max(m[i][j],z[i][j]));
		}
	cout<<ans<<endl;
}

小结

此题码量较大，细节较多。调试较困难，一遍AC较难。

但是是一道练习广搜的好题。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章
快来参与讨论吧