记忆化搜索 —— Leetcode 2684. 矩阵中移动的最大次数

题目如下：

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

• 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。

返回你在矩阵中能够 移动 的 最大 次数。

思路：按列层次搜索，设正在检索第k列，如果列内检测到一个从k-1列能走到的格子，那么去判断该格能走到k+1列的哪些元素，并标记这些可到达的格子。利用布尔矩阵去记录对应的原矩阵的格子是否能到达。如果第k列的所有格子都不能走到k+1列的所有格子，就停止搜索。

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int bfs(vector<vector<int>>& grid,vector<vector<bool>>& boolmap){
        int m = grid.size();//行
        int n = grid[0].size();//列
        int x = 0;
        bool go = true;
        while(x<n && go){
            go = false;
            for(int i=0;i<m;i++){
                if(boolmap[i][x]){
                    if(x+1<n && grid[i][x+1] > grid[i][x]){
                        boolmap[i][x+1]=true;
                        go = true;
                    }
                    if(x+1<n && i-1>=0 && grid[i-1][x+1] > grid[i][x]){
                        boolmap[i-1][x+1]=true;
                        go = true;
                    }
                    if(x+1<n && i+1<m && grid[i+1][x+1] > grid[i][x]){
                        boolmap[i+1][x+1]=true;
                        go = true;
                    }
                }
            }
            x++;
        }
        return x-1;
    }

    int maxMoves(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<bool>> boolmap(m,vector<bool>(n,false));
        for(int i=0;i<m;i++){
            boolmap[i][0] = true;
        }
        return bfs(grid,boolmap);
    }
};

记得初始化第一列都是可到达的格子，因为它们是起点。

感谢你能看到这里。