【搜索,Floodfill染色】Acwing2060 奶牛选美

原题链接

简而言之，就是求由X构成的两个集合之间的最短曼哈顿距离

#include

using namespace std;

typedef pair PII;

const int N = 55;
int n, m;
char g[N][N]; //存图
bool st[N][N]; //BFS的标记数组
int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
// a存放第一个集合中所有点的坐标
// b存放第二个集合中所有点的坐标
vector a, b;

//寻找两个斑点，并进行着色
void bfs(int x, int y, int k)
{
    queue q;
    if(!k) a.push_back({x, y}); //如果k为0，则加入到a中
    else b.push_back({x, y});//否则加入到b中
    
    q.push({x, y}); // vector中用的是push_back(),queue中直接push就行了
    st[x][y] = true;
    
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        int sx = t.first, sy = t.second;
        for(int i=0; i<4; i++)
        {
            int nx = sx+dx[i], ny = sy + dy[i];
            if(nx >=0 && nx=0 && ny > n >> m;
    for(int i=0; i>g[i]; //每次读入一行
    // t做标记，染色时候，判断在哪个集合
    int t=0;
    for(int i=0; i 
DFS做法：参考链接 
数据范围很小，可以DFS求出两块斑点内的所有点然后比较。复杂度为 O(nm)
 
#include 
#include 
using namespace std;
using T = pair;

const int N = 60;

const int dr[] = { -1, 0, 1, 0 }, dc[] = { 0, 1, 0, -1 };

int n, m;
char g[N][N];
bool st[N][N];
vector block[2];

void dfs (vector & block, int x, int y)
{
    st[x][y] = true;
    block.push_back({x, y});
    for (int i = 0; i < 4; i ++ )
    {
        int dx = x + dr[i], dy = y + dc[i];
        if (st[dx][dy] || dx < 1 || dx > n || dy < 1 || dy > m || g[dx][dy] != 'X') continue;
        dfs(block, dx, dy);
    }
}

int main ()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> (g[i] + 1);

    for (int i = 1, which = 0; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (!st[i][j] && g[i][j] == 'X') dfs(block[which ++], i, j);

    int dist = 1e9 + 10;
    for (T & a : block[0])
        for (T & b : block[1])
            dist = min(abs(a.first - b.first) + abs(a.second - b.second), dist);

    cout << dist - 1 << endl;
    return 0;
}