列表

详情

LCP 71. 集水器

字符串数组 shape 描述了一个二维平面中的矩阵形式的集水器，shape[i][j] 表示集水器的第 i 行 j 列为：

已知当隔板构成存储容器可以存水，每个方格代表的蓄水量为 2。集水器初始浸泡在水中，除内部密闭空间外，所有位置均被水填满。 现将其从水中竖直向上取出，请返回集水器最终的蓄水量。

注意：

示例 1：

输入： shape = ["....rl","l.lr.r",".l..r.","..lr.."]

输出：18

解释：如下图所示，由于空气会穿过隔板，因此红框区域没有水 image.png{:width="280px"}

示例 2：

输入： shape = [".rlrlrlrl","ll..rl..r",".llrrllrr","..lr..lr."] 输出：18

解释：如图所示。由于红框右侧未闭合，因此多余的水会从该处流走。 image.png{:width="400px"}

示例 3：

输入： shape = ["rlrr","llrl","llr."] 输出：6

解释：如图所示。 image.png{:width="230px"}

示例 4：

输入： shape = ["...rl...","..r..l..",".r.rl.l.","r.r..l.l","l.l..rl.",".l.lr.r.","..l..r..","...lr..."]

输出：30

解释：如下图所示。由于中间为内部密闭空间，无法蓄水。 image.png{:width="350px"}

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int reservoir(vector<string>& shape) { } };

golang 解法, 执行用时: 12 ms, 内存消耗: 5.9 MB, 提交时间: 2023-08-24 14:44:33 

func reservoir(shape []string) int {
	n, m := len(shape), len(shape[0])
	// 每个格子分成四个区域（上下左右），标上序号，方便用并查集连通
	// 假设左右下还有一圈格子，直接连到超级汇点 0
	u := make([][]int, n+1)
	d := make([][]int, n+1)
	l := make([][]int, n+1)
	r := make([][]int, n+1)
	for i := range u {
		u[i] = make([]int, m+2)
		d[i] = make([]int, m+2)
		l[i] = make([]int, m+2)
		r[i] = make([]int, m+2)
	}
	c := 1
	for i := 0; i < n; i++ {
		for j := 1; j <= m; j++ { // 假设格子的列号从 1 开始，这样方便表示左右边界
			u[i][j] = c; c++
			d[i][j] = c; c++
			l[i][j] = c; c++
			r[i][j] = c; c++
		}
	}

	// 并查集模板
	fa := make([]int, c)
	for i := range fa {
		fa[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if fa[x] != x {
			fa[x] = find(fa[x])
		}
		return fa[x]
	}
	merge := func(x, y int) { fa[find(x)] = find(y) }

	ok := make([]bool, c) // 能否容纳水
	// 倒着判断每一行，寻找可能有水的区域
	for i := n - 1; i >= 0; i-- {
		for j := 0; j <= m; j++ {
			merge(r[i][j], l[i][j+1]) // 连通左右
		}
		for j := 1; j <= m; j++ {
			merge(d[i][j], u[i+1][j]) // 连通下
			// 根据格子的类型连接格子内部四个区域
			switch shape[i][j-1] {
			case '.':
				merge(l[i][j], u[i][j])
				merge(l[i][j], d[i][j])
				merge(l[i][j], r[i][j])
			case 'l':
				merge(l[i][j], d[i][j])
				merge(r[i][j], u[i][j])
			default:
				merge(l[i][j], u[i][j])
				merge(r[i][j], d[i][j])
			}
		}
		for j := 1; j <= m; j++ {
			// 在没有连接第 i-1 行的情况下，无法到达左右下边界 => 能容纳水
			ok[l[i][j]] = find(l[i][j]) != find(0)
			ok[r[i][j]] = find(r[i][j]) != find(0)
			ok[u[i][j]] = find(u[i][j]) != find(0)
			ok[d[i][j]] = find(d[i][j]) != find(0)
		}
	}

	// 第一行连上超级汇点，方便后面统一判断是否在闭合区域里面
	for j := 1; j <= m; j++ {
		merge(u[0][j], 0)
	}

	ans := 0
	for i, b := range ok {
		if b && find(i) == find(0) { // 能容纳水，且不在闭合区域里面
			ans++
		}
	}
	return ans / 2
}

cpp 解法, 执行用时: 28 ms, 内存消耗: 9 MB, 提交时间: 2023-08-24 14:44:18 

class Solution {
public:
    int reservoir(vector<string> &shape) {
        int n = shape.size(), m = shape[0].size(), c = 1;
        // 每个格子分成四个区域（上下左右），标上序号，方便用并查集连通
        // 假设左右下还有一圈格子，直接连到超级汇点 0
        int u[n + 1][m + 2], d[n + 1][m + 2], l[n + 1][m + 2], r[n + 1][m + 2];
        memset(u, 0, sizeof(u)); memset(d, 0, sizeof(d)); memset(l, 0, sizeof(l)); memset(r, 0, sizeof(r));
        for (int i = 0; i < n; ++i)
            for (int j = 1; j <= m; ++j) // 假设格子的列号从 1 开始，这样方便表示左右边界
                u[i][j] = c++, d[i][j] = c++, l[i][j] = c++, r[i][j] = c++;

        // 并查集模板
        int fa[c];
        iota(fa, fa + c, 0);
        function<int(int)> find = [&](int x) -> int { return fa[x] == x ? x : fa[x] = find(fa[x]); };
        auto merge = [&](int x, int y) { fa[find(x)] = find(y); };

        bool ok[c]; // 能否容纳水
        memset(ok, 0, sizeof(ok));
        // 倒着判断每一行，寻找可能有水的区域
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j <= m; j++) merge(r[i][j], l[i][j + 1]); // 连通左右
            for (int j = 1; j <= m; j++) {
                merge(d[i][j], u[i + 1][j]); // 连通下
                // 根据格子的类型连接格子内部四个区域
                if (shape[i][j - 1] == '.') merge(l[i][j], u[i][j]), merge(l[i][j], d[i][j]), merge(l[i][j], r[i][j]);
                else if (shape[i][j - 1] == 'l') merge(l[i][j], d[i][j]), merge(r[i][j], u[i][j]);
                else merge(l[i][j], u[i][j]), merge(r[i][j], d[i][j]);
            }
            for (int j = 1; j <= m; j++) {
                // 在没有连接第 i-1 行的情况下，无法到达左右下边界 => 能容纳水
                ok[l[i][j]] = find(l[i][j]) != find(0);
                ok[r[i][j]] = find(r[i][j]) != find(0);
                ok[u[i][j]] = find(u[i][j]) != find(0);
                ok[d[i][j]] = find(d[i][j]) != find(0);
            }
        }

        // 第一行连上超级汇点，方便后面统一判断是否在闭合区域里面
        for (int j = 1; j <= m; j++) merge(u[0][j], 0);

        int ans = 0;
        for (int i = 0; i < c; i++)
            ans += ok[i] && find(i) == find(0); // 能容纳水，且不在闭合区域里面
        return ans / 2;
    }
};

java 解法, 执行用时: 11 ms, 内存消耗: 41.9 MB, 提交时间: 2023-08-24 14:43:55 

class Solution {
    private int[] fa;

    public int reservoir(String[] shape) {
        int n = shape.length, m = shape[0].length(), c = 1;
        // 每个格子分成四个区域（上下左右），标上序号，方便用并查集连通
        // 假设左右下还有一圈格子，直接连到超级汇点 0
        int[][] u = new int[n + 1][m + 2], d = new int[n + 1][m + 2], l = new int[n + 1][m + 2], r = new int[n + 1][m + 2];
        for (var i = 0; i < n; ++i)
            for (var j = 1; j <= m; ++j) {  // 假设格子的列号从 1 开始，这样方便表示左右边界
                u[i][j] = c++;
                d[i][j] = c++;
                l[i][j] = c++;
                r[i][j] = c++;
            }

        fa = new int[c];
        for (var i = 0; i < c; i++) fa[i] = i;

        var ok = new boolean[c]; // 能否容纳水
        // 倒着判断每一行，寻找可能有水的区域
        for (var i = n - 1; i >= 0; --i) {
            for (var j = 0; j <= m; j++)
                merge(r[i][j], l[i][j + 1]); // 连通左右
            for (var j = 1; j <= m; j++) {
                merge(d[i][j], u[i + 1][j]); // 连通下
                // 根据格子的类型连接格子内部四个区域
                var type = shape[i].charAt(j - 1);
                if (type == '.') {
                    merge(l[i][j], u[i][j]);
                    merge(l[i][j], d[i][j]);
                    merge(l[i][j], r[i][j]);
                } else if (type == 'l') {
                    merge(l[i][j], d[i][j]);
                    merge(r[i][j], u[i][j]);
                } else {
                    merge(l[i][j], u[i][j]);
                    merge(r[i][j], d[i][j]);
                }
            }
            for (var j = 1; j <= m; j++) {
                // 在没有连接第 i-1 行的情况下，无法到达左右下边界 => 能容纳水
                ok[l[i][j]] = find(l[i][j]) != find(0);
                ok[r[i][j]] = find(r[i][j]) != find(0);
                ok[u[i][j]] = find(u[i][j]) != find(0);
                ok[d[i][j]] = find(d[i][j]) != find(0);
            }
        }

        // 第一行连上超级汇点，方便后面统一判断是否在闭合区域里面
        for (var j = 1; j <= m; j++)
            merge(u[0][j], 0);

        var ans = 0;
        for (var i = 0; i < c; i++)
            if (ok[i] && find(i) == find(0))
                ++ans; // 能容纳水，且不在闭合区域里面
        return ans / 2;
    }

    private int find(int x) {
        if (fa[x] != x) fa[x] = find(fa[x]);
        return fa[x];
    }

    private void merge(int x, int y) {
        fa[find(x)] = find(y);
    }
}

python3 解法, 执行用时: 224 ms, 内存消耗: 18.1 MB, 提交时间: 2023-08-24 14:43:34 

class Solution:
    def reservoir(self, shape: List[str]) -> int:
        n, m = len(shape), len(shape[0])
        # 每个格子分成四个区域（上下左右），标上序号，方便用并查集连通
        # 假设左右下还有一圈格子，直接连到超级汇点 0
        u = [[0] * (m + 2) for _ in range(n + 1)]
        d = [[0] * (m + 2) for _ in range(n + 1)]
        l = [[0] * (m + 2) for _ in range(n + 1)]
        r = [[0] * (m + 2) for _ in range(n + 1)]
        c = 1
        for i in range(n):
            for j in range(1, m + 1):  # 假设格子的列号从 1 开始，这样方便表示左右边界
                u[i][j] = c; c += 1
                d[i][j] = c; c += 1
                l[i][j] = c; c += 1
                r[i][j] = c; c += 1

        # 并查集模板
        fa = list(range(c))
        def find(x: int) -> int:
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]
        def merge(x: int, y: int):
            fa[find(x)] = find(y)

        ok = [False] * c  # 能否容纳水
        # 倒着判断每一行，寻找可能有水的区域
        for i in range(n - 1, -1, -1):
            for j in range(m + 1):
                merge(r[i][j], l[i][j + 1])  # 连通左右
            for j, type in enumerate(shape[i], 1):
                merge(d[i][j], u[i + 1][j])  # 连通下
                # 根据格子的类型连接格子内部四个区域
                if type == '.':
                    merge(l[i][j], u[i][j])
                    merge(l[i][j], d[i][j])
                    merge(l[i][j], r[i][j])
                elif type == 'l':
                    merge(l[i][j], d[i][j])
                    merge(r[i][j], u[i][j])
                else:
                    merge(l[i][j], u[i][j])
                    merge(r[i][j], d[i][j])
            for j in range(1, m + 1):
                # 在没有连接第 i-1 行的情况下，无法到达左右下边界 => 能容纳水
                ok[l[i][j]] = find(l[i][j]) != find(0)
                ok[r[i][j]] = find(r[i][j]) != find(0)
                ok[u[i][j]] = find(u[i][j]) != find(0)
                ok[d[i][j]] = find(d[i][j]) != find(0)

        # 第一行连上超级汇点，方便后面统一判断是否在闭合区域里面
        for j in range(1, m + 1):
            merge(u[0][j], 0)

        ans = 0
        for i, b in enumerate(ok):
            if b and find(i) == find(0):  # 能容纳水，且不在闭合区域里面
                ans += 1
        return ans // 2

上一题

© 2024 leetcode.cn