计蒜客第三章：蒜头君回家

本文主要是介绍计蒜客第三章：蒜头君回家，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

计蒜客习题：蒜头君回家

题目

样例

题解

两次BFS打表，第一次从起点到钥匙，第二次从终点到钥匙，找出两个表相同位置加和最小的值。

代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,xx[7]={0,0,-1,1},num[2005][2005],yy[7]={1,-1,0,0},f=1,mi=5000000,v[2005][2005],key[2005][2005];
char mp[2005][2005];
struct point
{int x, y;point(int xx,int yy){x=xx;y=yy;}
};
void bfs(int sx,int sy)
{memset(v,0,sizeof(v));queue<point> q;q.push(point(sx,sy));v[sx][sy]=1;while(!q.empty()){int x=q.front().x;int y=q.front().y;q.pop();for(int i=0;i<4;i++){int tx=x+xx[i];int ty=y+yy[i];if(tx<1||tx>n||ty<1||ty>m) continue;if(!v[tx][ty]&&mp[tx][ty]!='#'){v[tx][ty]=1;if(!f) num[tx][ty]=num[x][y]+1;else key[tx][ty]=key[x][y]+1;q.push(point(tx, ty));}}}return;
}int main()
{int sx,sy,ex,ey;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>mp[i][j];if(mp[i][j]=='S') {sx=i;sy=j;}if(mp[i][j]=='T') {ex=i;ey=j;}}bfs(sx,sy);f=0;bfs(ex,ey);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]=='P'&&num[i][j]&&key[i][j]&&mi>num[i][j]+key[i][j]) mi=num[i][j]+key[i][j];cout<<mi;return 0;
}

这篇关于计蒜客第三章：蒜头君回家的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---