2022.10.12.-秋招-第三题-快递员

ID: 12

Difficulty: 7

题目内容

小红是一名快递员，他每天都要在城市里送很多快递。他负责的一个小区是一个很特别的地方，这个小区原本是一个军事基地，后来被改造成了住宅区。因为基地的设计很复杂，所以小区的布局也很奇怪，大体上可以看成一个 $m \times n$ 个方格组成的矩阵。有些地方还保留了原来的防御设施。这些设施对于普通人来说是不可进入的，所以小红不能穿过它们。(0 代表空地， B 代表楼栋, # 代表防御设施)

小区的住户大多数是退伍军人或者军人家属，他们都有一种特殊的习惯：他们不喜欢下楼取快递，而是要求小红把快递送到他们附近的某个地方，然后他们再去取。这是因为他们觉得下楼太麻烦，而且有些人还有战争创伤，不愿意和外界接触。小红虽然觉得这样很不合理，但是他也不敢得罪这些住户，只能尽量满足他们的要求。

小红每天都会从小区的一个入口开始送快递，这个入口的位置是 $[row,col]$ 。他可以在空地和楼栋之间自由移动，但是不能穿过防御设施。他的投递方式是这样的：他会在小区里选最多 $k$ 个派件点，然后通知周边楼栋的住户前来取件。派件点必须是空地或者楼栋，并且小红可以到达。通知范围是和派件点距离不超过 $s$ 的同一行或者同一列，并且没有被防御设施挡住的楼栋。

小红希望能够选择合适的派件点，使得他可以给最多楼栋派发快递，并且节省时间和精力。你能帮助小红吗？

输入描述

第一行：两个整数 $m$ 和 $n$ $(0\lt m,n \leq 9)$ ,代表小区的大小

第二行：两个整数 $row$ 和 $col$ $(0 \leq row \lt m,0 \leq col \lt n)$ ,代表快递员的初始位置

第三行：派件点数目 $k$ $(0 \lt k \leq 5)$

第四行：派件点可派件的最大距离 $s$ $(0 \lt s \leq 30)$

接下来是 $m$ 行 $n$ 列的矩阵，每一行的元素以空格分隔，内容为(0,B,#)

用例保证所有的输入在正常范围内。

输出描述

返回最多可派件的楼栋数量。

样例

输入

4 4
0 1
2
1
#0B#
0BB#
0#0#
B#B0

输出

题目描述

这道题目要求在一个 m × n 的矩阵中，选择最多 k 个派件点，使得派件点能够覆盖尽可能多的楼栋 (B)。派件点的覆盖范围是在同一行或同一列内，距离不超过 s 且不被防御设施 (#) 阻挡的楼栋。快递员只能移动到空地 (0) 或楼栋 (B) 上，不能穿过防御设施

思路

思路步骤 1.确定可达点：

使用广度优先搜索（BFS）从快递员的起始位置 [row, col] 出发，找到所有可以到达的点（0 或 B），这些点是潜在的派件点。

2.标记楼栋位置：

遍历整个矩阵，记录所有楼栋 (B) 的位置，并为每个楼栋分配一个唯一的编号，用于后续的位运算。

3.计算每个派件点的覆盖：

对于每个可达的派件点，计算其在同一行和同一列内，不超过 s 的距离且不被 # 阻挡的所有楼栋。使用位运算将这些楼栋的编号表示为一个位掩码（Bitmask）。

4.选择派件点：

使用回溯（DFS）或动态规划的方法，选择最多 k 个派件点，使得它们的覆盖位掩码的并集最大。由于 k 较小，可以通过组合枚举或贪心策略进行优化。 5.剪枝优化：

在搜索过程中，如果当前选择的派件点数量已达到 k，或无法超过当前已记录的最大覆盖数，立即停止该分支的搜索。

6.输出结果：

最终输出最大的覆盖楼栋数量。

#include <bits/stdc++.h>
using namespace std;
const int N = 35;
int n, m;
char a[N][N];
int k, s;
int ans;
bool ch(int x, int y) {		//检查(x,y)是否在图内并不是墙
	return min(x, y) >= 0 && x < n && y < m && a[x][y] != '#';
}
int dx[] = { 1,0,-1,0 };	//四个方向横坐标偏移量
int dy[] = { 0,1,0,-1 };	//纵坐标偏移量
bool bk[N][N];			//是否搜索过
vector<pair<int, int>> v;	//所有合法点集合
void dfs(int x, int y) {
	if (bk[x][y]) return;	//如果当前点搜索过直接return
	bk[x][y] = 1;		//标记为搜索过
	v.push_back({ x, y });	//放入点集
	for (int i = 0; i < 4; i++) {	//遍历四个方向
		int tx = x + dx[i], ty = y + dy[i];
		if (!ch(tx, ty)) continue;	//如果出地图或者是墙，继续遍历下一个方向
		dfs(tx, ty);	//dfs搜索
	}
}
void dfs2(int now, int cnt, int nows) {		//代表选到v中的第now个点，还剩cnt个派件点可以选，当前答案为nows
	if (cnt == 0 || now == v.size()) {	//如果选完了cnt个派件点或者遍历完所有的点
		ans = max(ans, nows);		//更新答案并返回
		return;
	}
	//剪枝，如果剩余的所有点都选满(4*s+1)个楼房还不比当前答案大，则直接返回
	if(nows + cnt*(4*s+1) <= ans)return;
	vector<pair<int, int>> fix;		//记录当前状态中被修改的点，用于dfs状态回溯
	for (int i = 0; i < 4; i++) {		//遍历四个方向各s格
		for (int j = 0; j <= s; j++) {
			int tx = v[now].first + dx[i] * j;
			int ty = v[now].second + dy[i] * j;
			if (!ch(tx, ty))break;		//如果出地图或者是墙，遍历下一个方向，break当前循环
			if (a[tx][ty] == 'B') {		//如果是楼，将当前楼置为空地防止重复计算
				fix.push_back({ tx, ty });	//放入fix中之后回溯时还原
				a[tx][ty] = '0';		//置为空地
			}
		}
	}
	dfs2(now + 1, cnt - 1, nows+fix.size());	//遍历下一个点，选了当前点，当前答案增加fix.size()
	for(auto g:fix) {		//还原
		a[g.first][g.second] = 'B';
	}
	dfs2(now + 1, cnt, nows);		//遍历下一个点，不选当前点，当前答案不变
}
int main()
{
	int x, y;
	cin >> n >> m >> x >> y >> k >> s;	//输入
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	dfs(x, y);		//搜索出所有的从起始点能到达的点。
	random_shuffle(v.begin(), v.end());		//随机排列一下，降低期望复杂度
	dfs2(0, k, 0);	//选出所有状态，更新答案
	cout << ans << endl;	//输出答案
}

python

import sys
import random

# 提高递归深度限制，防止递归过深导致的错误
sys.setrecursionlimit(1000000)

# 定义四个方向的移动（下、右、上、左）
dx = [1, 0, -1, 0]  # 下、右、上、左
dy = [0, 1, 0, -1]

# 全局变量初始化
n, m = 0, 0        # 地图的行数和列数
a = []             # 地图矩阵
k, s = 0, 0        # 派件点数量和覆盖范围
ans = 0            # 最大覆盖的楼栋数量
bk = []            # 是否搜索过的标记矩阵
v = []             # 所有可达的点集合

def ch(x, y):
    """
    检查坐标 (x, y) 是否在地图内且不是墙
    """
    return 0 <= x < n and 0 <= y < m and a[x][y] != '#'

def dfs(x, y):
    """
    深度优先搜索，收集所有从起始点可达的点
    :param x: 当前点的行坐标
    :param y: 当前点的列坐标
    """
    global ans
    if bk[x][y]:
        return  # 如果当前点已经被搜索过，直接返回
    bk[x][y] = True  # 标记当前点为已搜索
    v.append((x, y))  # 将当前点加入可达点集合
    for i in range(4):  # 遍历四个方向
        tx = x + dx[i]
        ty = y + dy[i]
        if ch(tx, ty):
            dfs(tx, ty)  # 递归搜索新的坐标

def dfs2(now, cnt, nows):
    """
    递归选择派件点的函数，尝试覆盖更多的楼栋
    :param now: 当前正在考虑的点在可达点集合中的索引
    :param cnt: 剩余可以选择的派件点数量
    :param nows: 当前已经覆盖的楼栋数量
    """
    global ans
    if cnt == 0 or now == len(v):
        # 如果没有剩余派件点可以选择，或者已经遍历完所有点
        ans = max(ans, nows)  # 更新答案
        return
    # 剪枝：如果即使选择剩余的所有派件点，每个派件点最多覆盖 (4*s +1) 个楼栋
    # 仍然无法超过当前的答案，则提前返回
    if nows + cnt * (4 * s + 1) <= ans:
        return
    fix = []  # 记录当前状态中被修改的楼栋，用于回溯
    x, y = v[now]  # 当前考虑的派件点坐标
    for i in range(4):  # 遍历四个方向
        for j in range(0, s + 1):  # 修正为从 j=0 开始，包含派件点自身
            tx = x + dx[i] * j
            ty = y + dy[i] * j
            if not ch(tx, ty):
                break  # 如果出地图或者遇到墙，停止该方向的遍历
            if a[tx][ty] == 'B':
                fix.append((tx, ty))  # 记录被覆盖的楼栋
                a[tx][ty] = '0'        # 将楼栋标记为已覆盖，防止重复计算
    # 选择当前派件点
    dfs2(now + 1, cnt - 1, nows + len(fix))
    # 回溯，恢复被覆盖的楼栋
    for g in fix:
        a[g[0]][g[1]] = 'B'
    # 不选择当前派件点
    dfs2(now + 1, cnt, nows)

def main():
    global n, m, k, s, ans, a, bk, v
    # 读取所有输入数据并分割为列表
    input_data = sys.stdin.read().split()
    idx = 0
    # 读取小区的行数和列数
    n = int(input_data[idx])
    m = int(input_data[idx + 1])
    idx += 2
    # 读取快递员的初始位置
    x = int(input_data[idx])
    y = int(input_data[idx + 1])
    idx += 2
    # 读取最多可以选择的派件点数量
    k = int(input_data[idx])
    # 读取派件点的覆盖范围
    s = int(input_data[idx + 1])
    idx += 2
    # 读取地图布局
    a = [['0' for _ in range(m)] for _ in range(n)]
    for i in range(n):
        if idx >= len(input_data):
            break
        line = input_data[idx]
        for j in range(m):
            if j < len(line):
                a[i][j] = line[j]
            else:
                a[i][j] = '0'  # 默认为空地
        idx += 1
    # 初始化标记矩阵和可达点集合
    bk = [[False for _ in range(m)] for _ in range(n)]
    v = []
    # 执行深度优先搜索，收集所有可达点
    if ch(x, y):
        dfs(x, y)
    # 随机打乱可达点顺序，降低期望复杂度
    random.shuffle(v)
    # 执行递归选择派件点，更新答案
    dfs2(0, k, 0)
    # 输出结果
    print(ans)

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    // 定义四个方向的移动（下、右、上、左）
    static int[] dx = {1, 0, -1, 0}; // 下、右、上、左
    static int[] dy = {0, 1, 0, -1};
    
    // 地图的行数和列数
    static int m, n;
    // 地图矩阵
    static char[][] a;
    // 派件点数量和覆盖范围
    static int k, s;
    // 最大覆盖的楼栋数量
    static int ans = 0;
    // 是否搜索过的标记矩阵
    static boolean[][] bk;
    // 所有可达的点集合
    static List<Point> v = new ArrayList<>();
    
    // Point 类表示坐标点
    static class Point {
        int x, y;
        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    
    /**
     * 检查坐标 (x, y) 是否在地图内且不是墙
     * @param x 行坐标
     * @param y 列坐标
     * @return 如果合法且不是墙，返回 true，否则返回 false
     */
    static boolean ch(int x, int y){
        return (0 <= x && x < m) && (0 <= y && y < n) && (a[x][y] != '#');
    }
    
    /**
     * 深度优先搜索，收集所有从起始点可达的点
     * @param x 当前点的行坐标
     * @param y 当前点的列坐标
     */
    static void dfs(int x, int y){
        if(bk[x][y]) return; // 如果当前点已经被搜索过，直接返回
        bk[x][y] = true; // 标记当前点为已搜索
        v.add(new Point(x, y)); // 将当前点加入可达点集合
        for(int i = 0; i < 4; i++){ // 遍历四个方向
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(ch(tx, ty)){
                dfs(tx, ty); // 递归搜索新的坐标
            }
        }
    }
    
    /**
     * 递归选择派件点的函数，尝试覆盖更多的楼栋
     * @param now 当前正在考虑的点在可达点集合中的索引
     * @param cnt 剩余可以选择的派件点数量
     * @param nows 当前已经覆盖的楼栋数量
     */
    static void dfs2(int now, int cnt, int nows){
        if(cnt == 0 || now == v.size()){
            // 如果没有剩余派件点可以选择，或者已经遍历完所有点
            ans = Math.max(ans, nows); // 更新答案
            return;
        }
        // 剪枝：如果即使选择剩余的所有派件点，每个派件点最多覆盖 (4*s +1) 个楼栋
        // 仍然无法超过当前的答案，则提前返回
        if(nows + cnt * (4 * s + 1) <= ans){
            return;
        }
        // 当前考虑的派件点坐标
        Point current = v.get(now);
        int x = current.x;
        int y = current.y;
        // 记录当前状态中被修改的楼栋，用于回溯
        List<Point> fix = new ArrayList<>();
        for(int i = 0; i < 4; i++){ // 遍历四个方向
            for(int j = 0; j <= s; j++){ // 修正为从 j=0 开始，包含派件点自身
                int tx = x + dx[i] * j;
                int ty = y + dy[i] * j;
                if(!ch(tx, ty)){
                    break; // 如果出地图或者遇到墙，停止该方向的遍历
                }
                if(a[tx][ty] == 'B'){
                    fix.add(new Point(tx, ty)); // 记录被覆盖的楼栋
                    a[tx][ty] = '0'; // 将楼栋标记为已覆盖，防止重复计算
                }
            }
        }
        // 选择当前派件点
        dfs2(now + 1, cnt - 1, nows + fix.size());
        // 回溯，恢复被覆盖的楼栋
        for(Point g : fix){
            a[g.x][g.y] = 'B';
        }
        // 不选择当前派件点
        dfs2(now + 1, cnt, nows);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 读取小区的行数和列数
        m = sc.nextInt();
        n = sc.nextInt();
        // 读取快递员的初始位置
        int row = sc.nextInt();
        int col = sc.nextInt();
        // 读取最多可以选择的派件点数量
        k = sc.nextInt();
        // 读取派件点的覆盖范围
        s = sc.nextInt();
        sc.nextLine(); // 读取换行符
        // 初始化地图矩阵
        a = new char[m][n];
        for(int i = 0; i < m; i++){
            String line = sc.nextLine();
            for(int j = 0; j < n; j++){
                if(j < line.length()){
                    a[i][j] = line.charAt(j);
                }
                else{
                    a[i][j] = '0'; // 默认为空地
                }
            }
        }
        // 初始化标记矩阵
        bk = new boolean[m][n];
        // 执行深度优先搜索，收集所有可达点
        if(ch(row, col)){
            dfs(row, col);
        }
        // 随机打乱可达点顺序，降低期望复杂度
        Collections.shuffle(v, new Random());
        // 执行递归选择派件点，更新答案
        dfs2(0, k, 0);
        // 输出结果
        System.out.println(ans);
        sc.close();
    }
}

#P1588. 2022.10.12.-秋招-第三题-快递员

题目内容

输入描述

输出描述

样例

题目描述

思路

python

java

Status

Development

Support