P4668

Cutata · 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;
}