P2774 Grid Number Picking Problem

There is an $m$-row $n$-column grid, with a positive integer in each cell. You need to pick numbers from the grid so that no two chosen cells share a common edge, and the total sum of the chosen numbers is maximized. Please compute the maximum possible sum.

The first line contains two integers separated by a space, representing the number of rows $m$ and the number of columns $n$. From line $2$ to line $(m + 1)$, each line contains $n$ integers. The $j$-th integer on line $(i + 1)$ represents the number in the cell at row $i$, column $j$, namely $a_{i, j}$.

Output a single integer on one line, representing the maximum sum.

Constraints For $100\%$ of the testdata, it is guaranteed that $1 \leq n, m \leq 100$, $1 \leq a_{i, j} \leq 10^5$. Tip Please note that in the first line, $m$ is read before $n$. Translated by ChatGPT 5