AcWing 2060. 奶牛选美（DFS）

题目链接

思路

先DFS染色，将这两部分分开，分别用1和2标记，然后对于第一堆的每个元素直接用BFS跑一个最短路即可

代码

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"

const int N = 100;

char mp[N][N];
int a[N][N];
int n,m;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

bool vis[N][N];

bool check(int x,int y) {
	if(x >= 1 && x <= n && y >= 1 && y <= m) return true;
	return false;
}

void dfs(int x,int y,int k) {
	if(vis[x][y] || mp[x][y] != 'X') return;
	vis[x][y] = true;
	mp[x][y] = '.';
	a[x][y] = k;
	for(int i = 0;i < 4; ++i) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(check(nx,ny))
			dfs(nx,ny,k);
	}
}

int ans = 0x3f3f3f3f;

struct Node {
	int x,y,step;
};



int bfs(int x,int y) {
	queue<Node> que;
	que.push({x,y,0});
	while(!que.empty()) {
		Node p = que.front();
		que.pop();
		if(vis[p.x][p.y]) continue;
		vis[p.x][p.y] = true;
		if(a[p.x][p.y] == 2) {
			return p.step;
		}
		for(int i = 0;i < 4; ++i) {
			int nx = p.x + dx[i];
			int ny = p.y + dy[i];
			if(check(nx,ny) && a[nx][ny] != 1) {
				que.push({nx,ny,p.step+1});
			}
		}
	}
	return 0x3f3f3f3f;
}

int main()
{
	cin>>n>>m;
	for(int i = 1;i <= n; ++i) {
		for(int j = 1;j <= m; ++j) {
			cin>>mp[i][j];
		}
	}
	int k = 1;
	for(int i = 1;i <= n; ++i) {
		for(int j = 1;j <= m; ++j) {
			if(mp[i][j] == 'X') {
				dfs(i,j,k);
				k++;
			}
		}
	}
//	puts("------------line begin--------------");
//	for(int i = 1;i <= n; ++i) {
//		for(int j = 1;j <= m; ++j) {
//			cout<<a[i][j]<<" \n"[j==m];
//		}
//	}
//	puts("------------line end--------------");
	int ans = 0x3f3f3f3f;
	memset(vis,0,sizeof vis);
	for(int i = 1;i <= n; ++i) {
		for(int j = 1;j <= m; ++j) {
			if(a[i][j] == 1) {
				k = bfs(i,j);
				ans = min(ans,k);
				memset(vis,0,sizeof vis);
			}
		}
	}
	cout<<ans-1<<endl;
	
	return 0;
}

/*

14 35
...................................
..................................X
..................................X
..................................X
................................X.X
................................XXX
...........X.X..................XXX
.......XXXXXXX.................XXXX
........XXXXXX..............XXX.XXX
........XXXXX...............XXXXX.X
......XXXXXXXX............X.XXXXXXX
....XXXXXXXXXX............XX.XXXXXX
...XXXXXXXXXXXXXX.........XXXXXXXXX
...XXXXXXXX.X..X.........XXXXXXXXXX
*/