长丰网站建设,公共服务平台登录入口,企业主体负责人和网站负责人,滁州哪里做网站题目分析 1.双重bfs,遍历两个起点求最短路再计算总和即可 2.唯一的坑点在于对于一个KFC#xff0c;两人中可能有一个到不了#xff0c;所以还要对到不了的点距离做处理 #include bits/stdc.h
using namespace std;
using ll long long;
const int N 220;struct pos… 题目分析 1.双重bfs,遍历两个起点求最短路再计算总和即可 2.唯一的坑点在于对于一个KFC两人中可能有一个到不了所以还要对到不了的点距离做处理 #include bits/stdc.h
using namespace std;
using ll long long;
const int N 220;struct pos{int y, x;
}Y, M;char g[N][N];
bool vis[N][N];
int disy[N][N];
int dism[N][N];
int t1, t2;int dx[] {0, 0, 1, -1};
int dy[] {1, -1, 0, 0};void bfs1()
{memset(vis, 0, sizeof vis);queuepos q;q.push(Y);vis[Y.y][Y.x] 1;while(!q.empty()){pos temp q.front(); q.pop();for(int i 0; i 4; i){int a temp.x dx[i]; int b temp.y dy[i];if(a 1 || b 1 || a t2 || b t1) continue;if(!vis[b][a] g[b][a] ! #){vis[b][a] 1;q.push({b, a});disy[b][a] disy[temp.y][temp.x] 1;}}}for(int i 1; i t1; i){for(int j 1; j t2; j){if(disy[i][j] 0) disy[i][j] 1e7;}}
}void bfs2()
{memset(vis, 0, sizeof vis);queuepos q;q.push(M);vis[M.y][M.x] 1;while(!q.empty()){pos temp q.front(); q.pop();for(int i 0; i 4; i){int a temp.x dx[i]; int b temp.y dy[i];if(a 1 || b 1 || a t2 || b t1) continue;if(!vis[b][a] g[b][a] ! #){vis[b][a] 1;q.push({b, a});dism[b][a] dism[temp.y][temp.x] 1;}}}for(int i 1; i t1; i){for(int j 1; j t2; j){if(dism[i][j] 0) dism[i][j] 1e7;}}}int main()
{while(scanf(%d %d, t1, t2) ! EOF){memset(disy, 0, sizeof disy);memset(dism, 0, sizeof dism);for(int i 1; i t1; i) for(int j 1; j t2; j){scanf( %c, g[i][j]);if(g[i][j] Y) Y.x j, Y.y i;else if(g[i][j] M) M.x j, M.y i;}bfs1();bfs2();int ans 999;for(int i 1; i t1; i){for(int j 1; j t2; j){if(g[i][j] ) ans min(ans, disy[i][j] dism[i][j]);}}printf(%d\n, ans * 11);}}
