# LeetCode 2684. Maximum Number of Moves in a Grid

https://leetcode.com/problems/maximum-number-of-moves-in-a-grid/description/

## 題目大意

給定一個 $m \times n$ 的矩陣 `grid` 其中包含正整數

可以從矩陣的第一列中的任意一格開始，依以下方式遍歷矩陣：

從當前格 `(row, col)`，你可以移動到以下任一格：`(row - 1, col + 1)`、`(row, col + 1)` 和 `(row + 1, col + 1)`，前提是移動到的格的數值必須**嚴格大於**當前格的數值

回傳最多可以做幾動？

## 思考

class Solution
{
public:
    int maxMoves(vector<vector<int>> &grid)
    {
        const int m = grid.size();
        const int n = grid.begin()->size();
        bitset<1001> curr, next;

        for (int i = 0; i < m; ++i)
        {
            curr.set(i);
        }

        for (int j = 0; j < n - 1; ++j)
        {
            next.reset();
            for (int i = 0; i < m; ++i)
            {
                if (curr[i])
                {
                    for (int k = i - 1; k <= i + 1; ++k)
                    {
                        if (k >= 0 && k < m && grid[i][j] < grid[k][j + 1])
                            next.set(k);
                    }
                }
            }

            if (next.none())
                return j;

            curr = next;
        }

        return n - 1;
    }
};

Go 參考解答：

func maxMoves(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])

	curr := make([]bool, m)
	for i := 0; i < m; i++ {
		curr[i] = true
	}

	for j := 0; j < n-1; j++ {
		next := make([]bool, m)
		for i := 0; i < m; i++ {
			if curr[i] {
				for k := i - 1; k <= i+1; k++ {
					if k >= 0 && k < m && grid[i][j] < grid[k][j+1] {
						next[k] = true
					}
				}
			}
		}

		if !contains(next) {
			return j
		}

		curr = next
	}

	return n - 1
}

func contains(arr []bool) bool {
	for _, val := range arr {
		if val {
			return true
		}
	}
	return false
}