7.29日课堂总结 - 洛谷保存站

## P1746 离开中山路

###  题意简化
> 给定一个 $n \times m$ 的地图，地图中的每个格子要么是一个障碍物 $1$ ，要么是一个空地 $0$ 。你需要从起点 $(x_1,y_1)$ 移动到终点 $(x_2,y_2)$ ，移动时只能上下左右四个方向移动，且不能穿过障碍物。请问最少需要多少步才能到达终点 B。

### 思路
> 这道题可以使用广度优先搜索（BFS）来解决。我们从起点开始，使用队列来存储当前的位置和步数，然后不断探索四个方向的相邻节点，直到找到终点。

### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
int vis[1010][1010];
char a[1010][1010];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};
struct node{
    int x,y,step;//(x,y)坐标和步数step
};
void bfs(int x,int y,int hx,int hy){
    queue<node> q;//队列存储当前节点
	q.push({x,y,0});//将起点入队
	vis[x][y]=1;
	while(q.size()){
		node f=q.front();
		q.pop();
		if(f.x==hx&&f.y==hy){//如果到达终点
			cout<<f.step;。//输出步数
			return;//结束函数
		}
		for(int i=0;i<4;i++){
			int xx=f.x+dx[i];
			int yy=f.y+dy[i];
			if(xx>0&&xx<=n&&yy>0&&yy<=n&&vis[xx][yy]==0&&a[xx][yy]!='1'){//检查边界和是否访问过和是否是障碍物
				q.push({xx,yy,f.step+1});//将相邻节点入队
				vis[xx][yy]=1;//标记为已访问
			}
		}
	}
	return;
}
int main(){
    cin>>n;//输入地图大小
    int x1,y1,x2,y2;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];//输入地图
        }
    }
    cin>>x1>>y1>>x2>>y2;//输入起点和终点坐标
    bfs(x1,y1,x2,y2);//调用BFS函数
    return 0;
}
```

## P10487 Nightmare II

### 题意简化
> 给定一个 $n \times m$ 的地图，地图中的每个格子有空着'.'、障碍物 'X' 和移动点 'A'、移动点 'B'、阻挡点 'Z'。你需要从起点 A 移动到终点 B，移动时A能上下左右四个方向三步,需要$1s$，B能上下左右四个方向一步,需要$1s$。Z是阻挡点，每$1s$会向上下左右四个方向分裂，A和B都不能经过。请问最少需要多少秒A和B才能相遇。  
> 注意：A和B可以同时移动。

### 思路
> 这道题可以使用广度优先搜索（BFS）来解决。我们从起点 A 和 B 开始，使用队列来存储当前的位置和步数，然后不断探索四个方向的相邻节点，直到找到相遇点。但需要注意的是，A 和 B 的移动方式不同，A 每次可以移动三步，而 B 每次只能移动一步。因此，我们需要分别对 A 和 B 进行 BFS，并在每次扩展时考虑到它们的移动方式。由于 Z 是阻挡点，我们需要在 BFS 中处理 Z 的分裂情况，我们发现可以通过曼哈顿距离来判断Z的影响范围。

### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int sx1,sy1,sx2,sy2;// A 的起点和 B 的起点
bool vis[1010][1010];// 访问标记数组
int dis[2][1010][1010];// dis[k][x][y] 表示从起点 k 到 (x,y) 的最短距离
char a[1010][1010];// 地图数组
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};
struct node{
	int x,y;// 坐标
};
vector<node> op;// 存储阻挡点 Z 的位置
int n,m;
bool check1(int x,int y,int t){
	for(int i=0;i<=1;i++){
		if(abs(op[i].x-x)+abs(op[i].y-y)<=2*t) return 1;// 检查 (x,y) 是否在阻挡点 Z 的影响范围内
	}
	return 0;
}
bool check2(int x,int y){
	return (x>=1&&x<=n&&y>=1&&y<=m&&vis[x][y]==0&&a[x][y]!='X');// 检查 (x,y) 是否在地图范围内且未被访问且不是障碍物
}
void bfs(int sx,int sy,int k){
	memset(vis,0,sizeof(vis));
	dis[k][sx][sy]=0;
	vis[sx][sy]=1;
	queue<node> q;
	q.push({sx,sy});
	int tim=0;
	while(q.size()){
		tim++;
		int cnt=3;// A 每次扩展 3 次
		if(k) cnt=1;// 如果是 B，则每次只扩展 1 次
		while(cnt--){
			int len=q.size();
			while(len--){
				node u=q.front();// 取出队首元素
				q.pop();// 弹出队首元素
				for(int i=0;i<4;i++){
					int xx=u.x+dx[i];
					int yy=u.y+dy[i];
					if(!check1(u.x,u.y,tim)&&check2(xx,yy)){// 检查 (xx,yy) 是否在阻挡点 Z 的影响范围内且在地图范围内且未被访问且不是障碍物
						dis[k][xx][yy]=tim;// 更新最短距离
						vis[xx][yy]=1;// 标记为已访问
						q.push({xx,yy});// 将 (xx,yy) 入队
					}
				}
			}
		}
	}
	return;
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='M'){// M 是起点 A
				sx1=i;
				sy1=j;
			}
			if(a[i][j]=='G'){// G 是起点 B
				sx2=i;
				sy2=j;
			}
			if(a[i][j]=='Z'){// Z 是阻挡点
				op.push_back({i,j});
			}
		}
	}
	memset(dis,-1,sizeof(dis));// 初始化距离数组为 -1
	bfs(sx1,sy1,0);// 对 A 进行 BFS
	bfs(sx2,sy2,1);// 对 B 进行 BFS
	int minn=1e9;// 初始化最小值为一个很大的数
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(dis[0][i][j]==-1||dis[1][i][j]==-1) continue;
			minn=min(minn,max(dis[0][i][j],dis[1][i][j]));// 更新最小值为 A 和 B 到 (i,j) 的最大距离
		}
	}
	if(minn==1e9) cout<<-1<<'\n';// 如果最小值仍然是初始值，说明无法相遇
	else cout<<minn<<'\n';// 输出最小值
	op.clear(); 
}
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
    return 0;
}
```

正在渲染内容...