AcWing 2060. 奶牛选美
原题链接
中等
作者:
locked
,
2024-03-14 21:24:00
,
所有人可见
,
阅读 12
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 55;
char g[N][N];
int n, m;
vector<PII> points[2];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void dfs(int x, int y, vector<PII> &t) {
t.push_back({x, y});
g[x][y] = '.';
for (int i = 0; i < 4; i ++ )
if(x + dx[i] < n && y + dy[i] < m && g[x+dx[i]][y+dy[i]] == 'X')
dfs(x+dx[i], y+dy[i], t);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
int k = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == 'X')
dfs(i, j, points[k++]);
int res = 100;
for (auto &i : points[0])
for (auto &j : points[1])
res = min(res, abs(i.first - j.first) + abs(i.second - j.second));
cout << res - 1;
return 0;
}