【无标题】_q619718

irpas 02-07 2938

给定一个?n?行?m?列的方格矩阵。

其中有些方格是空地（可以进入），有些方格是餐厅（可以进入），有些方格是障碍（不可进入）。

开始时，小?Y?和小?M?各自位于一个空地方格中。

每个人都可以沿上下左右四个方向进行移动，移动一格距离需要花费?1111?分钟时间。

他们希望选择一家餐厅进行聚餐，要求两人从各自出发点到达该餐厅所花费的时间之和尽可能小。

输出这个最小时间和。

输入格式

输入包含多组测试数据。

每组数据第一行包含两个整数?n,m。

接下来?n?行，包含一个?n×m?的字符矩阵。

矩阵中只包含以下五种字符：

#?表示障碍方格。.?表示空地方格。Y?表示小?Y所在的空地方格，有且仅有一个。M?表示小?M?所在的空地方格，有且仅有一个。@?表示餐厅。

输出格式

每组数据输出一行答案，表示最小时间和。

保证一定有解。

数据范围

最多包含?100100?组数据。 2≤n,m≤200。

输入样例：

4 4 Y.#@ .... .#.. @..M 4 4 Y.#@ .... .#.. @#.M 5 5 Y..@. .#... .#... @..M. #...#

输出样例：

66 88 66

注意判断每一个餐厅需要判断非0?

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> #include <queue> #include <set> #include <map> #include <stack> using namespace std; constexpr int N=200+7; //#define int long long typedef pair<int,int>PII; int n,m; char a[210][210]; int dx[4]={1,0,0,-1},dy[4]={0,1,-1,0}; int st[210][210]; int ans1[210][210],ans2[210][210]; void bfs1(int x,int y,int ans[][210]){ memset(st, 0, sizeof st); queue<PII>q; q.push({x,y}); st[x][y]=1; while(q.size()){ auto t=q.front(); q.pop(); for(int i=0;i<4;i++){ int xx=t.first+dx[i],yy=t.second+dy[i]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!st[xx][yy]&&a[xx][yy]!='#'){ st[xx][yy]=1; q.push({xx,yy}); ans[xx][yy]=ans[t.first][t.second]+1; } } } } signed main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); while (cin >> n >> m) { memset(ans1, 0, sizeof ans1); memset(ans2, 0, sizeof ans2); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i][j] == 'Y') { bfs1(i, j, ans1); } else if (a[i][j] == 'M') { bfs1(i, j, ans2); } } } int res = 1e5; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (a[i][j] == '@'&&ans1[i][j]&&ans2[i][j]) { res = min(res, (ans1[i][j] + ans2[i][j])); } } } cout << res * 11 << endl; } return 0; }