题目链接
// 总体思路如下:
// 根据题目意思,这道题最主要的不是距离最短,而是超市数量要最少
// 那么如何让超市数量最少呢,其实很简单,就是同一连通区域中只开一家超市
// 然后去找在这个区域内只开一家超市去其他房子的最短距离
// 这样一来问题就变成了找连通区域,然后再找连通区域中放置一个超市到其他房子的最短距离
// 那么区域数就是超市数,所有区域的距离和起来的答案就是最短距离
// 本题中遍历连通区域用dfs,找最短距离用bfs
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<climits>
using namespace std;
int n;
// 用dfs来遍历某一连通区域,并且找出能建超市的点位
void dfs(vector<vector<char>>& dfs_map, vector<pair<int, int>>& points, int x, int y) {
if(x >= n || x < 0 || y >= n || y < 0 || dfs_map[x][y] == '*') {
return;
}
points.push_back(make_pair(x, y));
dfs_map[x][y] = '*';
dfs(dfs_map, points, x, y + 1);
dfs(dfs_map, points, x, y - 1);
dfs(dfs_map, points, x + 1, y);
dfs(dfs_map, points, x - 1, y);
}
void solve() {
vector<vector<char>> map(n, vector<char>(n, ' ')); // 原始地图
vector<vector<char>> dfs_map(n, vector<char>(n, ' ')); // 用来给dfs找连通区域的地图,运行dfs函数以后会让该区域所有点都变成'*'
vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 方向,用来模拟上下左右走
// 读入数据
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
cin >> map[i][j];
dfs_map[i][j] = map[i][j];
}
}
int min_market = 0; // 最少超市数量,即区域数量
int min_distance = 0;// 最短距离
// 遍历所有点
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
// 如果该点有房屋, 意味着找到了一片连通区域, 此区域需要建造一所超市
// 我们将用dfs遍历该区域并且找到所有可能建造超市的点位
if(dfs_map[i][j] == '#') {
min_market++; // 找到区域,超市数+1
vector<pair<int, int>> points; // 储存点位
dfs(dfs_map, points, i, j); // 遍历区域找点位
int min_step = INT_MAX; // 用来记录该连通区域的最短距离
// 遍历所有可能点位, 找到该区域中的最短距离
for(auto point : points) {
vector<vector<bool>> visited(n, vector<bool>(n, false)); // 记录已经走过的点
queue<pair<int, int>> que; // bfs需要用的队列
que.push(point);
visited[point.first][point.second] = true; // 每次一放入点位就要置为true,防止超时
int steps = 0; // 用来记录超市到某一个房屋的距离
int dis = 0; // 用来记录在这个点位时超市到区域内所有房屋的总距离
while(!que.empty()) {
int size = que.size();
for(int k = 0; k < size; ++k) {
pair<int, int> p = que.front();
que.pop();
int x = p.first;
int y = p.second;
// 找到房屋,总距离增加
if(map[x][y] == '#') {
dis += steps;
}
// 模拟上下左右走并且将点位放入que队列
for(auto direction : directions) {
int nx = x + direction.first;
int ny = y + direction.second;
if(nx >= n || nx < 0 || ny >= n || ny < 0 || map[nx][ny] == '*' || visited[nx][ny] == true) {
continue;
}
que.push(make_pair(nx, ny));
// 一放入点位就要置为true
visited[nx][ny] = true;
}
}
// 每一圈加一步
steps++;
}
// 取该区域所有点位中到房屋的最短距离
min_step = min(min_step, dis);
}
// 加上已经求出来的某一区域的最短距离
min_distance += min_step;
}
}
}
cout << min_market << " " << min_distance << endl;
}
int main() {
while(cin >> n) {
solve();
}
return 0;
} import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 就是原来的map
char[][] map = new char[n][n];
// DFS遍历用的map1, 所以会被修改为全是*
char[][] map1 = new char[n][n];
int[][] H = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 超市的最小数量
int ans1 = 0;
// 最小的距离之和
int ans2 = 0;
for (int i = 0; i < n; i++) {
map[i] = sc.next().toCharArray();
map1[i] = map[i].clone();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map1[i][j] == '#') {
ans1++; //统计区域数量
// list存放所有可能放置商店的位置;
List<int[]> list = new ArrayList();
dfs(map1, i, j, list);
// 到这里dfs已经完了，接下来是bfs
// 每个区域总的最小距离
int min = Integer.MAX_VALUE;
for (int[] coordinate : list) {
// 每个位置的最小距离
int min1 = 0;
// 每个点距离商店的步数
int step = 0;
// 标记是否走过;
boolean[][] flag = new boolean[n][n];
// BFS独有的队列;
LinkedList<int[]> queue = new LinkedList<>();
queue.offer(coordinate);
// 标记加入的位置为走过;
flag[coordinate[0]][coordinate[1]] = true;
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {
int[] poll = queue.poll();
int x = poll[0], y = poll[1];
if (map[x][y] == '#') {
min1 += step;
}
for (int l = 0; l < 4; l++) {
int x2 = x + H[l][0];
int y2 = y + H[l][1];
if (x2 < 0 || y2 < 0 || x2 >= n || y2 >= n || map[x2][y2] == '*' || flag[x2][y2] == true) {
continue;
}
queue.offer(new int[]{x2, y2});
flag[x2][y2] = true;
}
}
step++;
}
//在不同位置的距离总和，找出最小值
min = Math.min(min1, min);
}
ans2 += min;
}
}
}
System.out.println(ans1 + " " + ans2);
}
public static void dfs(char[][] map, int x, int y, List<int[]> list) {
int n = map.length;
if (x < 0 || x >= n || y < 0 || y >= n || map[x][y] == '*') {
return;
}
list.add(new int[]{x, y});
map[x][y] = '*';
dfs(map, x - 1, y, list);
dfs(map, x + 1, y, list);
dfs(map, x, y - 1, list);
dfs(map, x, y + 1, list);
}
}###################
# 29
###################
from collections import deque
def dfs(graph, pair, visited, tmp):
x, y = pair
if x<0 or y<0 or x>=len(graph) or y>=len(graph[0]) or visited[x][y]:
return
if graph[x][y] == '*':
visited[x][y] = True
return
tmp.append(pair)
visited[x][y] = True
dfs(graph=graph, pair=(x+1, y), visited=visited, tmp=tmp)
dfs(graph=graph, pair=(x-1, y), visited=visited, tmp=tmp)
dfs(graph=graph, pair=(x, y+1), visited=visited, tmp=tmp)
dfs(graph=graph, pair=(x, y-1), visited=visited, tmp=tmp)
n = int(input())
graph = []
for i in range(int(n)):
graph.append(list(input()))
# 先用dfs统计超市数量，然后使用bfs每个字图，得到最短距离
market = 0
distance = 0
visited = [[False for _ in range(n)] for _ in range(n)]
for i in range(n):
for k in range(n):
if visited[i][k] == False:
if graph[i][k] == '#':
tmp = []
dfs(graph=graph, pair=(i, k), visited=visited, tmp=tmp)
market+=1
tmp_distance = float('inf')
for p in tmp:
market_x, market_y = p
if graph[market_x][market_y] != "*":
p_distance = 0
queue = deque([(p, 0)])
visited_bfs = [[False for _ in range(n)] for _ in range(n)]
tmp_set = set(tmp)
while len(queue)!=0:
pair, count = queue.popleft()
x, y = pair
if pair not in tmp_set or visited_bfs[x][y]:
continue
visited_bfs[x][y] = True
if graph[x][y] == '#':
p_distance += count
queue.append(((x+1, y), count+1))
queue.append(((x-1, y), count+1))
queue.append(((x, y+1), count+1))
queue.append(((x, y-1), count+1))
tmp_distance = min(tmp_distance, p_distance)
distance += tmp_distance
else:
visited.append((i, k))
print(market, distance)const readline = require('readline')
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
})
let ks = -1
let count = 0 //代表每一行
let arr
function processInput() {
rl.on('line', function (data) {
if(ks === -1){
ks = Number(data)
arr = new Array(ks).fill().map(item=>new Array(ks).fill())
}else {
let ans1 = 0 //超市的最小数量
let ans2 = 0 //最小的距离之和
let row = data.split('')
let H = [[-1, 0], [1, 0], [0, -1], [0, 1]]
arr[count] = row
count++
if(count === ks){
let arr1 = JSON.parse(JSON.stringify(arr))
//arr数组收集完毕
for(let i = 0; i<ks; i++){
for(let j = 0; j<ks; j++){
//如果此处是房子，淹没该区域
if(arr1[i][j] === '#'){
ans1++ //超市的数量
let list = []
dfs(arr1, i, j, list)
//每个区域总的最小的距离
let min = Infinity
for(let z = 0; z<list.length; z++){
// 每个位置的最小距离
let min1 = 0
// 每个点距离商店的步数
let step = 0
let flag = new Array(ks).fill(false).map(item => new Array(ks).fill(false))
let queue = []
queue.push(list[z])
let a = list[z][0]
let b = list[z][1]
flag[a][b]= true
while(queue.length > 0){
let size = queue.length
for(let k = 0; k<size; k++){
let cur = queue.shift()
let x = cur[0]
let y = cur[1]
if(arr[x][y] == '#'){
min1 += step
}
for(let l = 0; l<4; l++){
let x2 = x + H[l][0]
let y2 = y + H[l][1]
if(x2 < 0 || y2 < 0 || x2 >= ks || y2 >= ks)
{
continue
}
if(flag[x2][y2] === true)
continue
if(arr[x2][y2] == '*')
continue
queue.push([x2, y2])
flag[x2][y2] = true
}
}
step++
}
min = Math.min(min1, min)
}
ans2 += min
}
}
}
console.log(ans1, ans2)
ks = -1
}
}
})
}
function dfs(arr1, i, j, list){
let n = arr1.length
// 越界
if(i < 0 || j < 0 || i >= n || j>= n){
return
}
// 此处是障碍
if(arr1[i][j] === '*'){
return
}
list.push([i, j])
arr1[i][j] = '*'
dfs(arr1, i-1, j, list)
dfs(arr1, i+1, j, list)
dfs(arr1, i, j-1, list)
dfs(arr1, i, j+1, list)
}
processInput()