AcWing 2060. 奶牛选美
原题链接
中等
作者:
._7623
,
2024-10-16 20:04:22
,
所有人可见
,
阅读 2
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
#include <climits>
#include <string>
#include <stack>
using namespace std;
using ll = long long;
const int N = 55;
int n, m;
int vis[N][N];
string s[N];
const int tx[] = { 1,-1,0,0 }, ty[] = { 0,0,1,-1 };
vector<pair<int, int>>ve1, ve2;
void dfs1(int x, int y) {
if (x < 0 || y < 0 || x >= n || y >= m) return;
if (vis[x][y]||s[x][y]=='.') return;
vis[x][y] = 1;
ve1.push_back({ x,y });
for (int i = 0; i < 4; i++) {
dfs1(x + tx[i], y + ty[i]);
}
}
int mini = 50000;
void solve() {
int i,flag=0, j;
cin >> n >> m;
for (i = 0; i < n; i++) {
cin >> s[i];
}
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (s[i][j] == 'X') {
if(flag==0)dfs1(i,j);
flag = 1;
if (vis[i][j] == 0) ve2.push_back({ i,j });
}
}
}
for (i = 0; i < ve1.size(); i++) {
for (j = 0; j < ve2.size(); j++) {
int t = abs(ve1[i].first - ve2[j].first) + abs(ve1[i].second - ve2[j].second);
if (t < mini) {
mini = t;
}
}
}
cout << mini-1 << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}