题解 | #wyh的吃鸡#

wyh的吃鸡

https://ac.nowcoder.com/acm/problem/15445

Bfs入门题具体思路为，从起点到终点有两种走法

一种是直接步行从起点走到终点

一种是先步行到某辆车的位置，再走到终点

由于n<=100，一次bfs的复杂为 $O (n^{2})$ ,T<=10,汽车的数量又小于100，可以算出最坏时间复杂度为1e7左右，轻松过时限

我们可以先算出从起点到每个点的距离，再枚举车的位置，算出车到终点的距离，最终到终点的距离取最小

具体代码如下

#include<bits/stdc++.h>
#define pii pair<int,int>
#define  fi first
#define  se second
#define int long long
using namespace std;
const int N=110;
string s[N];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool vis[N][N];
int dis[N][N];
int n,ans;
bool Ju(int x,int y){
    if(x<1||x>n||y<1||y>n) return false;
    if(s[x][y-1]=='O') return false;
    return true;
}
void bfs1(int sx,int sy)
{
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            dis[i][j]=1e9+7;
    dis[sx][sy]=0;
    queue< pair<pii,int> > q;
    q.push({{sx,sy},0});
    vis[sx][sy]=true;

    while(q.size())
    {
        auto t=q.front().fi;
        auto temp=q.front().se;
        //cout << t.fi << " " << t.se << endl;
        if(s[t.fi][t.se-1]=='X')ans=min(ans,1LL*2*temp);
        q.pop();
        for(int k=0;k<4;++k)
        {
            int xx=t.fi+dir[k][0];
            int yy=t.se+dir[k][1];
            if(xx<1||xx>n||yy<1||yy>n)continue;
            if(s[xx][yy-1]=='O')continue;
            if(dis[xx][yy]>temp+1)
            {
                dis[xx][yy]=temp+1;
                q.push({{xx,yy},temp+1});
            }
        }
    }
    return;
}
int bfs(int sx,int sy)//查询车到终点的时间
{
    memset(vis,0,sizeof vis);
    queue< pair<pii,int> > q;
    q.push({{sx,sy},0});
    vis[sx][sy]=true;

    while(q.size())
    {
        auto t=q.front().fi;
        auto temp=q.front().se;
        if(s[t.fi][t.se-1]=='X')
            return temp;
        q.pop();
        for(int k=0;k<4;++k)
        {
            int xx=t.fi+dir[k][0];
            int yy=t.se+dir[k][1];
            if(xx<1||xx>n||yy<1||yy>n)continue;
            if(vis[xx][yy]||s[xx][yy-1]=='O')continue;

            vis[xx][yy]=true;
            q.push({{xx,yy},temp+1});
        }
    }
    return 1LL<<61;
}
void solve()
{
    int k;cin >> n >> k;
    int sx,sy,ex,ey;

    for(int i=1;i<=n;++i)
        cin >> s[i];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
    if(s[i][j-1]=='S'){sx=i;sy=j;}
    else if(s[i][j-1]=='X'){ex=i;ey=j;}

    ans=1LL<<61;
    bfs1(sx,sy);

    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            if(s[i][j-1]=='C')
            {
                ans=min(ans,dis[i][j]*2+bfs(i,j));
            }

        }
    if(ans<=k)
    {
        cout << "YES\n";
        cout << ans << "\n";
    }
    else cout << "NO\n";

}
signed main()
{
    int T=1;cin >> T;
    while(T--)
    {
        solve();
    }
}

顺带一提，当我换了一种方式判断这个点是不是终点的时候第二组数据死活过不去，希望评论区的大佬能指点一下下面的代码哪里出错了

#include<bits/stdc++.h>
#define pii pair<int,int>
#define  fi first
#define  se second
#define int long long
using namespace std;
const int N=110;
string s[N];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
bool vis[N][N];
int dis[N][N];
int n,ans;
bool Ju(int x,int y){
    if(x<1||x>n||y<1||y>n) return false;
    if(s[x][y-1]=='O') return false;
    return true;
}
void bfs1(int sx,int sy)
{
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            dis[i][j]=1e9+7;
    dis[sx][sy]=0;
    queue< pair<pii,int> > q;
    q.push({{sx,sy},0});
    vis[sx][sy]=true;

    while(q.size())
    {
        auto t=q.front().fi;
        auto temp=q.front().se;
        //cout << t.fi << " " << t.se << endl;
        if(s[t.fi][t.se-1]=='X')ans=min(ans,1LL*2*temp);
        q.pop();
        for(int k=0;k<4;++k)
        {
            int xx=t.fi+dir[k][0];
            int yy=t.se+dir[k][1];
            if(xx<1||xx>n||yy<1||yy>n)continue;
            if(s[xx][yy-1]=='O')continue;
            if(dis[xx][yy]>temp+1)
            {
                dis[xx][yy]=temp+1;
                q.push({{xx,yy},temp+1});
            }
        }
    }
    return;
}
int sx,sy,ex,ey;
int bfs(int sx,int sy)
{
    memset(vis,0,sizeof vis);
    queue< pair<pii,int> > q;
    q.push({{sx,sy},0});
    vis[sx][sy]=true;

    while(q.size())
    {
        auto t=q.front().fi;
        auto temp=q.front().se;
        if(ex==t.fi&&ey==t.se)///与上面那份代码只在这里有区别
            return temp;
        q.pop();
        for(int k=0;k<4;++k)
        {
            int xx=t.fi+dir[k][0];
            int yy=t.se+dir[k][1];
            if(xx<1||xx>n||yy<1||yy>n)continue;
            if(vis[xx][yy]||s[xx][yy-1]=='O')continue;

            vis[xx][yy]=true;
            q.push({{xx,yy},temp+1});
        }
    }
    return 1LL<<61;
}
void solve()
{
    int k;cin >> n >> k;


    for(int i=1;i<=n;++i)
        cin >> s[i];
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(s[i][j-1]=='S'){sx=i;sy=j;}
            else if(s[i][j-1]=='X'){ex=i;ey=j;}

    ans=1LL<<61;
    bfs1(sx,sy);

    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            if(s[i][j-1]=='C')
            {
                ans=min(ans,dis[i][j]*2+bfs(i,j));
            }

        }
    if(ans<=k)
    {
        cout << "YES\n";
        cout << ans << "\n";
    }
    else cout << "NO\n";

}
signed main()
{
    int T=1;cin >> T;
    while(T--)
    {
        solve();
    }
}