京东算法岗9.17笔试AC代码

第一题：
多重背包问题，有n件不同的装备，每件装备花费p_i，增加魅力值c_i，最多购买s_i件。
单测试用例。第一行输入两个以空格分隔的整数n, p，分别表示装备数和最多可花的金钱。
第2行到n+1行，每一行输入以空格分隔的三个整数，分别表示购买数量限制，价格，魅力值。

思路：
多重背包问题模板题。

示例：
输入：
3 10
2 2 3
1 5 10
2 4 12

输出：
27

代码：

def f(bags, V):
    n = len(bags)
    dp = [0] * (V+1)
    for i in range(n):
        p, v, s = bags[i]
        if s*v >= V:
            for j in range(v, V+1, 1):
                dp[j] = max(dp[j], dp[j-v] + p)
        else:
            for j in range(V, v - 1, -1):
                for k in range(min(s, j//v) + 1):
                    dp[j] = max(dp[j], dp[j-k*v] + k*p)
    return dp[V]

N, V = list(map(int, input().split()))
bags = []
for _ in range(N):
    s, v, p = list(map(int, input().split()))
    if v > V: continue
    bags.append((p, v, s))
res = f(bags, V)
print(res)

第二题：
给定一张带有障碍物的地图和王子与公主的位置，问王子能否见到公主的位置。若能，返回"YES"，否则返回"NO"。"S"表示王子的位置，"E"表示公主的位置，"."表示可以通行，"#"表示陷阱。
多个测试用例。第一行输入T表示测试用例数。
接下来每组测试用例输入n+1行。
第一行输入空格分隔的两个数n, m分别表示地图的行数和列数。
第2到n+1行，每行输入一个长度为m的字符串。

思路：
用并查集表示公主与王子两个点是否联通即可。然后用DFS或者BFS去遍历与他们其中一人相联通的所有可行点即可。代码给出了DFS与BFS两种方式，速度相同。

示例：
输入：
1
10 10
.....S.#..
....###...
..##.....E
...####...
.....####.
###...##..
..##...##.
.####..##.
......##..
####.....#

输出：
"YES"

代码：

class unionFind():
    def __init__(self, grid):
        n, m = len(grid), len(grid[0])
        self.root = [-1] * (m * n)
        self.rank = [1] * (m * n)
        for i in range(n):
            for j in range(m):
                k = i * j + j
                self.root[k] = k

    def find(self, p):
        if self.root[p] != p:
            self.root[p] = self.find(self.root[p])
        return self.root[p]

    def union(self, x, y):
        rootx, rooty = self.find(x), self.find(y)
        if rootx != rooty:
            if self.rank[rootx] < self.rank[rooty]:
                rootx, rooty = rooty, rootx
            self.root[rooty] = rootx
            if self.rank[rootx] == self.rank[rooty]:
                self.rank[rootx] += 1

    def isConnected(self, x, y):
        return self.find(x) == self.find(y)


def dfs(grid, i, j, uf):
    k = i * j + j
    for x, y in [(i, j + 1), (i - 1, j), (i, j - 1), (i + 1, j)]:
        if 0 <= x < n and 0 <= y < m and grid[x][y] == '.':
            grid[i][j] = '#'
            t = x * y + y
            uf.union(k, t)
            dfs(grid, x, y, uf)


def f(grid):
    case = "BFS"
    uf = unionFind(grid)
    ps, pe = -1, -1
    sx, sy, ex, ey = -1, -1, -1, -1
    for i in range(n):
        for j in range(m):
            k = i * j + j
            if grid[i][j] == 'S':
                grid[i][j] = '.'
                ps, sx, sy = k, i, j
            elif grid[i][j] == 'E':
                pe, ex, ey = k, i, j
                grid[i][j] = '.'

    # 76ms
    if case == "BFS":
        stack = [(sx, sy)]
        while stack:
            px, py = stack.pop()
            k = px*py + py
            for x, y in [(px, py + 1), (px - 1, py), (px, py - 1), (px + 1, py)]:
                if 0 <= x < n and 0 <= y < m and grid[x][y] == '.':
                    stack.append((x, y))
                    grid[px][py] = '#'
                    t = x * y + y
                    uf.union(k, t)

    # 76ms
    elif case == "DFS":
        dfs(grid, sx, sy, uf)

    res = "YES" if uf.isConnected(ps, pe) else "NO"
    return res


T = eval(input())
for _ in range(T):
    n, m = list(map(int, input().split()))
    grid = []
    for i in range(n):
        line = "?".join(input())
        l = line.split("?")
        grid.append(l)
    out = f(grid)
    print(out)