自动搬运

查看原文

来自洛谷，原作者为

	Cutata 祈禳

搬运于2025-08-24 22:02:28，当前版本为作者最后更新于2022-08-19 15:03:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

• 本题翻译不全，重点：$Y$ 是你的船，$V$ 是贼船，$I$ 是岛屿，$T$ 是宝藏；你需要尽可能避免贼船攻击到你的船，并拿到宝藏。
• 贼船的攻击范围：以它能走到的每个点为中心，分别画一条垂直线和水平线，直到碰到边界或岛屿才停止。
• 由第三个样例可以看出，如果你的船出现在贼船下一步的攻击范围内，你同样会挂，所以本题可以理解为贼船先走。

题目分析

• 本题与求最短路思想类似，并且数据范围 $1 \le N,M \le 700$，可以直接宽搜。
• 涉及到两个点的移动，为了提高效率，可以采取同步宽搜的方法，即定义两个队列，对它们同时进行入队出队操作。
• 优先对贼船的队列进行扩展，将其攻击范围打上标记。判出条件：你的船的队列为空（或者头指针 $>$ 尾指针），注意与贼船的队列无关。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 700 + 10;
bool visp[MAXN][MAXN], visq[MAXN][MAXN], tmap[MAXN][MAXN];
struct node{
	int x, y, step;
}q[MAXN * MAXN], p[MAXN * MAXN];
int n, m, ansx, ansy, frontp = 1, rearp = 1, frontq = 1, rearq = 1, tx, ty, nx, ny;
int dx[] = {0, 0, 1, 0, -1};
int dy[] = {0, 1, 0, -1, 0};
bool checkp(int x, int y)//判断贼船是否能走
{
	if(x < 1 or x > n or y < 1 or y > m or visp[x][y] or tmap[x][y])
	    return false;
	return true;
}
bool checkq(int x, int y)//判断你的船是否能走
{
	if(x < 1 or x > n or y < 1 or y > m or visq[x][y] or tmap[x][y])
	    return false;
	return true;
}
bool checkt(int x, int y)//判断贼船是否能攻击此格
{
	if(x < 1 or x > n or y < 1 or y > m or tmap[x][y])
	    return false;
	return true;
}
void bfs()
{
	while(frontq <= rearq){//判出
		for(int i = 0; i < 5; i++){//先对贼船队列进行扩展
			tx = p[frontp].x + dx[i];
			ty = p[frontp].y + dy[i];
			if(checkp(tx, ty)){
				rearp++;
				p[rearp].x = tx;
				p[rearp].y = ty;
				p[rearp].step = p[frontp].step + 1;
				visp[tx][ty] = visq[tx][ty] = true;
				nx = tx, ny = ty;
				while(checkt(nx - 1, ny)){//对四个方向进行攻击
					nx--;
					visq[nx][ny] = true;
				}
				nx = tx, ny = ty;
				while(checkt(nx, ny - 1)){
					ny--;
					visq[nx][ny] = true;
				}
				nx = tx, ny = ty;
				while(checkt(nx + 1, ny)){
					nx++;
					visq[nx][ny] = true;
				}
				nx = tx, ny = ty;
				while(checkt(nx, ny + 1)){
					ny++;
					visq[nx][ny] = true;
				}
			}
		}
		for(int i = 1; i < 5; i++){//对你的船的队列进行扩展
			tx = q[frontq].x + dx[i];
			ty = q[frontq].y + dy[i];
			if(checkq(tx, ty)){
				rearq++;
				q[rearq].x = tx;
				q[rearq].y = ty;
				q[rearq].step = q[frontq].step + 1;
				visq[tx][ty] = true;
				if(q[rearq].x == ansx and q[rearq].y == ansy){//找到宝藏
			        cout << "YES";
			        return;
		        }
			}
		}
		frontp++;
		if(q[frontq + 1].step < p[frontp].step)
		    frontq++, frontp--;//算法核心，保证两艘船的行动在同一时刻
	}
	cout << "NO";
}
int main()
{
	ios::sync_with_stdio(false);//优化，打消输入输出缓存
	cin >> n >> m;
	char ch;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> ch;
			if(ch == '.')
			    continue;
			if(ch == 'Y'){
				q[1].x = i;
				q[1].y = j;
				visq[i][j] = true;
			}
			else if(ch == 'V'){
				p[1].x = i;
				p[1].y = j;
				visq[i][j] = true;
			}
			else if(ch == 'I')
			    tmap[i][j] = true;
			else{
				ansx = i;
				ansy = j;
			}	
	    }
	}
	bfs();
	return 0;
}