LCR 130. 衣橱整理(中等)

Posted on In Views:

1，问题描述

LCR 130. 衣橱整理

难度：中等

家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid，其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。

整理规则为：在整理过程中，可以选择 向右移动一格 或 向下移动一格，但不能移动到衣柜之外。同时，不需要整理 digit(i) + digit(j) > cnt 的格子，其中 digit(x) 表示数字 x 的各数位之和。

请返回整理师 总共需要整理多少个格子。

示例 1：

1
2
输入：m = 4, n = 7, cnt = 5
输出：18

提示：

  • 1 <= n, m <= 100
  • 0 <= cnt <= 20

2，初步思考

​ 使用广度有限搜索（bfs）、深度优先搜索（dfs）进行处理

3，代码处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import support.Pair;

import java.util.ArrayDeque;
import java.util.Deque;

public class _LCR130衣橱整理 {

    // 广度优先搜索
    // 使用一个队列进行缓存下一层需要处理的节点
    public int wardrobeFinishing_bfs(int m, int n, int cnt) {
        sum = 0;
        int maxCnt = Math.max(m, n);
        int[] digitCache = new int[maxCnt + 1];
        boolean[][] visited = new boolean[m][n];
        Deque<Pair<Integer, Integer>> queue = new ArrayDeque<>();// 广度优先搜索
        queue.add(new Pair<>(0, 0));
        while (!queue.isEmpty()) {
            Pair<Integer, Integer> poll = queue.poll();
            int i = poll.getKey();
            int j = poll.getValue();
            if (i < m && j < n && !visited[i][j] && (getDigit(digitCache, i) + getDigit(digitCache, j)) <= cnt) {
                sum++;
                visited[i][j] = true;
                queue.add(new Pair<>(i + 1, j));
                queue.add(new Pair<>(i, j + 1));
            }
        }
        return sum;
    }


    // 深度优先搜索
    public int wardrobeFinishing_dfs(int m, int n, int cnt) {
        sum = 0;
        int maxCnt = Math.max(m, n);
        int[] digitCache = new int[maxCnt + 1];
        boolean[][] visited = new boolean[m][n];
        dfs(visited, digitCache, m, n, 0, 0, cnt);
        return sum;
    }

    int sum = 0;

    private void dfs(boolean[][] visited, int[] dp, int m, int n, int i, int j, int cnt) {
        if (i < m && j < n && !visited[i][j] && (getDigit(dp, i) + getDigit(dp, j)) <= cnt) {
            sum++;
            visited[i][j] = true;
            dfs(visited, dp, m, n, i + 1, j, cnt);
            dfs(visited, dp, m, n, i, j + 1, cnt);
        }
    }

    private int getDigit(int[] dp, int i) {
        if (dp[i] != 0) return dp[i];
        int s = 0;
        int idx = i;
        for (; i != 0; i /= 10) s += i % 10;
        dp[idx] = s;
        return s;
    }

    public static void main(String[] args) {
        _LCR130衣橱整理 lcr130衣橱整理 = new _LCR130衣橱整理();
        System.out.println(lcr130衣橱整理.wardrobeFinishing_dfs(16, 8, 4));
//        System.out.println(lcr130衣橱整理.wardrobeFinishing(4, 7, 5));
    }
}