题目

思路

分为两段，先从S找到p，再从T找到p，然后取这两段距离和的最小值就是最小步数。
为了可以重复使用bfs函数，减少代码，我们使用一个三维数组cnt的第三位来表示没取到q和取到了q前后两个状态。

注意1：不能直接从s搜索到最近的一个p，然后从T搜索到一个最近的p，然后将两个距离相加，因为不能保证这两个搜索到的p是同一个p

注意2：一开始的时候，要把cnt的所有值最大，memset(cnt,INF,sizeof(cnt))，原因是因为题中要求最小步数，如果某个p被#围住，那么他的cnt[][][0]和cnt[][][1]都为0，导致最后结果不对。

代码

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>//memset头文件
using namespace std;
const int INF=0x3f3f3f3f;
int n,m;
char mp[2005][2005];
bool vis[2005][2005];
int cnt[2005][2005][2];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void bfs(int xx,int yy,int s){//cnt[][][0]标记S到所有P点的步数 cnt[][][1]标记T到所有P点的步数。
    queue<pair<int,int> >q;
    q.push(make_pair(xx,yy));
    cnt[xx][yy][s]=0;
    vis[xx][yy]=1;
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int i=0;i<4;i++){
            int tx=dir[i][0]+x;
            int ty=dir[i][1]+y;
            if(tx>=0 && tx<n && ty>=0 && ty<m && !vis[tx][ty] && mp[tx][ty]!='#'){
                vis[tx][ty]=1;
                int a=cnt[x][y][s];
                cnt[tx][ty][s]=a+1;
                q.push(make_pair(tx,ty));
            }
        }
    }
}
int main(){
    cin>>n>>m;
    int sx,sy;
    int tx,ty;
    memset(cnt,INF,sizeof(cnt));//这里要让cnt最开始都为最大值，为什么？
    queue<pair<int,int> >q;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='P'){
                q.push(make_pair(i,j));//吧P点存取来
            }
            else if(mp[i][j]=='S'){
                sx=i;
                sy=j;
            }
            else if(mp[i][j]=='T'){
                tx=i;
                ty=j;
            }
        }
    }
   
    bfs(sx,sy,0);
   
    for(int i=0;i<n;i++){//memset(vis,0,sizeof(vis));
        for(int j=0;j<m;j++){
            vis[i][j]=0;
        }
    }
    bfs(tx,ty,1);
    int ans=0x3f3f3f3f;// 表示最大值的意思
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        ans=min(ans,cnt[x][y][0]+cnt[x][y][1]);//将两次bfs的cnt的步数相加，取所有的最小值。
    }
    cout<<ans<<endl;
    cout<<cnt[2][66][0]<<" "<<cnt[2][66][1]<<endl;
    return 0;
}

最后

以上就是靓丽煎饼为你收集整理的【计蒜客】蒜头君回家题目思路代码的全部内容，希望文章能够帮你解决【计蒜客】蒜头君回家题目思路代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。