1706.球会落何处

链接：1706.球会落何处
难度：Medium
标签：数组、矩阵、模拟
简介：返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。

题解 1 - cpp

• 编辑时间：2022-02-24
• 执行用时：28ms
• 内存消耗：13MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
   public:
    int n, m, check[100][100][4] = {0}, mmap[100][100][4] = {0};
    int dfs(vector<vector<int>>& grid, int row, int col, int idx) {
        if (mmap[row][col][idx]) return mmap[row][col][idx];
        int ans = -1;
        check[row][col][idx] = 1;
        if (grid[row][col] == 1) {
            if ((idx == 0 || idx == 3) && col < m - 1 &&
                check[row][col + 1][1] == 0) {
                ans = dfs(grid, row, col + 1, 1);
            } else if ((idx == 1 || idx == 2) && row < n - 1 &&
                       check[row + 1][col][0] == 0) {
                ans = dfs(grid, row + 1, col, 0);
            }
        } else {
            if ((idx == 0 || idx == 1) && col > 0 &&
                check[row][col - 1][3] == 0) {
                ans = dfs(grid, row, col - 1, 3);
            } else if ((idx == 2 || idx == 3) && row < n - 1 &&
                       check[row + 1][col][0] == 0) {
                ans = dfs(grid, row + 1, col, 0);
            }
        }
        check[row][col][idx] = 0;
        return mmap[row][col][idx] = ans;
    }
    vector<int> findBall(vector<vector<int>>& grid) {
        n = grid.size();
        m = grid[0].size();
        vector<int> ans(m);
        for (int col = 0; col < m; col++) {
            if (grid[n - 1][col] == 1) {
                mmap[n - 1][col][1] = mmap[n - 1][col][2] = col + 1;
            } else {
                mmap[n - 1][col][2] = mmap[n - 1][col][3] = col + 1;
            }
        }
        for (int col = 0; col < m; col++) {
            int val = dfs(grid, 0, col, 0);
            if (val > 0) val -= 1;
            ans[col] = val;
        }
        return ans;
    }
};