AcWing 2060. 奶牛选美 bfs使我旋转
原题链接
中等
作者:
虫师
,
2024-03-14 20:32:43
,
所有人可见
,
阅读 24
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int N, M;
char graph[60][60];
vector<PII> points[2];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
void bfs(int i, int j, vector<PII> &point)
{
queue<PII> q;
q.push({i, j});
point.push_back({i, j});
graph[i][j] = '.';
while (!q.empty())
{
int sz = q.size();
for (int i = 0; i < sz; i++)
{
PII cur = q.front();
q.pop();
for (int j = 0; j < 4; j++)
{
int next_x = cur.first + dx[j];
int next_y = cur.second + dy[j];
if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= M)
continue;
if (graph[next_x][next_y] == '.')
continue;
q.push({next_x, next_y});
point.push_back({next_x, next_y});
graph[next_x][next_y] = '.';
}
}
}
}
int main(void)
{
cin >> N >> M;
getchar();
for (int i = 0; i < N; i++)
scanf("%s", graph[i]);
int k = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (graph[i][j] == 'X')
bfs(i, j, points[k++]);
}
}
int res = 110;
for (PII &a : points[0])
for (PII &b : points[1])
res = min(res, abs(a.first - b.first) + abs(a.second - b.second) - 1);
cout << res;
return 0;
}