bcoi系列目录直达

首先是题目链接

OK呀目录^[1]

以下是题目描述:^[2]

题目背景

2024年1月19日广附紫兰信奥队的集训教室突然来了一只漂亮的猫咪，不知何故这只猫咪的一只眼睛受到了非常严重的伤害。信奥队的同学们都非常担心这只可怜的猫咪，有的同学从家里拿了猫粮给它吃，我们善良美丽的吴老师专门带着这只可怜的流浪猫咪去宠物医院帮它治疗眼睛。猫咪也很乖，我们在上课的时候，它就乖乖的呆在电脑桌下面，慢慢的这只独眼猫咪跟着D老师也学会了神奇的信奥算法，并在信奥界所向披靡，成为我们紫兰信奥队的海盗队长信奥怪猫侠。从此信奥的江湖就有了猫哥的传说......

题目描述

某天校园里出现了一只老鼠，我们需要帮助这只独眼海盗队长信奥怪猫侠去抓住这只老鼠，现给定一张$n*m$格的地图表示校园，地图由'#'，'.'，'' 组成，'#'表示围墙，''表示我们信奥队的一位同学所在位置，'.'表示独眼海盗队长信奥怪侠猫无法逾越的障碍物。信奥队员为了能帮助猫咪需要先清除这些障碍物，但是每位同学目前信奥魔力值还不够，同学们清理障碍物的时候就像大家做信奥题一样暂时还不会拐弯，也就是他们只能清理他所在格子的上下左右四个直线方向的障碍物，而且直到遇到墙壁就停止。现在告诉你猫的位置(catx,caty)和老鼠的位置(mousex,mousey)，猫只能沿着上下左右是个方向走，求猫能否抓到老鼠，如果能就输出猫的最小的方案步数，否则输出"No"。

输入格式

第一行输入两个数字n,m;

接下来输入n行m列的地图

最后一行输出四个数，分别表示catx,caty,mousex,mousey;

Output

猫抓到老鼠的最小步数或者"No"

样例

输入数据 1

6 6
......
#.*...
......
..#...
.#...*
......
1 3 6 6

输出数据 1

9

样例说明

样例中同学们清理完障碍物后用'o'表示通路，红色路线就是猫捉老鼠的路线。

..o..o
#o*ooo
..o..o
..#..o
.#ooo*
.....o

Limitation

$1≤n,m≤20$

=======================================================

好眼熟的猫

好了回归正题^[3]

题目要求猫哥去吃老鼠(内心PS:紫兰信奥队的海盗队长信奥怪猫侠居然亲自下场，这敌人可太敌人了)，途中猫哥不能穿越或穿透障碍物，但是有着善良大方体贴友好和蔼可亲平易近人乐于助人热心肠无私奉献敢于担当的同学清除障碍物

读题

同学们清理障碍物的时候就像大家做信奥题一样暂时还不会拐弯，也就是他们只能清理他所在格子的上下左右四个直线方向的障碍物，而且直到遇到墙壁就停止。

这说明同学会将TA所处行和列的障碍物清理(只要他没碰到墙)掉给猫哥抓老鼠吃

用广搜处理本题

特别鸣谢:代码参考于@

以下是gsx整理的代码:^[4]

#include <bits/stdc++.h>
using namespace std;
int n,m,cnt,sx,sy,ex,ey;
int dx[]={0, 0, 0, 1, -1};
int dy[]={0, 1, -1, 0, 0};
char g[35][35];
struct stu{int x,y,step;};
bool vis[35][35];
bool add(int x,int y){
    if(x<1 || x>n || y<1 || y>m) return 1;
    return 0;
}
bool out(int x,int y){
    if(add(x,y)) return 0;
    if(g[x][y] == '#')return 0;
    return 1;
}
bool out_cat(int x, int y){
    if(add(x,y))return 0;
    if(g[x][y]!='o')return 0;
    if(vis[x][y])return 0;
    return 1;
}
void c(int x,int y){
    g[x][y]='o';
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        while(out(nx,ny)==true){
            if(g[nx][ny]=='.') g[nx][ny] = 'o';
            nx+=dx[i];
            ny+=dy[i];
        }
    }
}

int bfs(int sx,int sy){
    queue <stu> q;
    vis[sx][sy]=1;
    q.push({sx,sy,1});
    while(!q.empty()){
        stu f=q.front();
        q.pop();
        if(f.x==ex && f.y==ey) return f.step;
        for(int i=1;i<=4;i++){
            int nx=f.x+dx[i];
            int ny=f.y+dy[i];
            if(out_cat(nx,ny)){
                vis[nx][ny]=1;
                q.push({nx,ny,f.step+1});
            }
        }
    }
    return -1;
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>g[i][j];

    for(int i=1; i<=n;i++)
        for(int j=1;j<=m;j++)
            if(g[i][j]=='*') c(i,j);

    cin>>sx>>sy>>ex>>ey;
    int ans=bfs(sx,sy);
    if(ans==-1)cout<<"No";
    else cout<<ans;
    return 0;
}

代码解析^[5]

以下这一大坨都是判断是否犯法的，具体参考注释

bool add(int x,int y){//判出界
    if(x<1 || x>n || y<1 || y>m) return 1;
    return 0;
}
bool out(int x,int y){//清理障碍碰到墙？
    if(add(x,y)) return 0;
    if(g[x][y] == '#')return 0;
    return 1;
}
bool out_cat(int x, int y){//遇到未清理障碍物？
    if(add(x,y))return 0;
    if(g[x][y]!='o')return 0;
    if(vis[x][y])return 0;
    return 1;//能走
}

e这处是善良大方体贴友好和蔼可亲平易近人乐于助人热心肠无私奉献敢于担当的同学清除障碍物的代码

void c(int x,int y){
    g[x][y]='o';//原点打标记
    for(int i=1;i<=4;i++){
        int nx=x+dx[i];//方向
        int ny=y+dy[i];
        while(out(nx,ny)==true){
            if(g[nx][ny]=='.') g[nx][ny] = 'o';//清理
            nx+=dx[i];
            ny+=dy[i];
        }
    }
}

广搜套模板就行，然后改一些条件，具体参考注释

int bfs(int sx,int sy){//广搜套模板
    queue <stu> q;
    vis[sx][sy]=1;//务必加，已查
    q.push({sx,sy,1});
    while(!q.empty()){
        stu f=q.front();
        q.pop();
        if(f.x==ex && f.y==ey) return f.step;//结束
        for(int i=1;i<=4;i++){
            int nx=f.x+dx[i];
            int ny=f.y+dy[i];
            if(out_cat(nx,ny)){
                vis[nx][ny]=1;
                q.push({nx,ny,f.step+1});
            }
        }
    }
    return -1;//猫哥不彳亍啊
}

总结^[6]

整套流程就是这样了

不知道下次能不能出个鱼的题目(awa,开个玩笑)

@

完工！

---

1. 目录，点击回去开头 ↩︎

2. 题目描述 ↩︎

3. 回归正题 ↩︎

4. 废话完了上代码 ↩︎

5. 代码解析 ↩︎

6. 总结 ↩︎