这道题也是题目就暗示了做法。这么大的图，走法太多，DFS肯定不行。只能递推找最优解。如果只能向右和向下就比较直接了，每一个格子的最优解药么从上面走要么从左边走。多了一个方向，在同一列里面可以上下走，把中间的那些行，分成两道题，一个是只能往下走，一个网上走，两个结果再比较一下，比较大的留下。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x * f;
}
int main() {
    int h = read(), w = read();
    long long max_last_col[h], max_this_col_from_top[h], max_this_col_from_btm[h];
    int a[h][w];
    for (register int i = 0; i < h; i++)
        for (register int j = 0; j < w; j++) a[i][j] = read();
    for (register int x = 0; x < w; x++) {
        if (x == 0) { //第一列，只有一个方向。
            max_last_col[0] = a[0][0];
            for (register int y = 1; y < h; y++)
                max_last_col[y] = a[y][0] + max_last_col[y - 1];
        } else if (x == w - 1) { //最后一列也只有一个方向走。懒得简化了
            max_this_col_from_top[0] = max_last_col[0] + a[0][x];
            for (register int y = 1; y < h; y++) {
                max_this_col_from_top[y] = max(
                                               max_last_col[y],
                                               max_this_col_from_top[y - 1]
                                           ) + a[y][x];
            }
        } else { //中间这些列，先从上往下走
            max_this_col_from_top[0] = max_last_col[0] + a[0][x];
            for (register int y = 1; y < h; y++) {
                max_this_col_from_top[y] = max(
                                               max_last_col[y],
                                               max_this_col_from_top[y - 1]
                                           ) + a[y][x];
            }//再从下往上找最优值
            max_this_col_from_btm[h - 1] = max_last_col[h - 1] + a[h - 1][x];
            for (register int y = h - 2; y >= 0; y--) {
                max_this_col_from_btm[y] = max(
                                               max_this_col_from_btm[y + 1],
                                               max_last_col[y]
                                           ) + a[y][x];
            }//最后看看两个方向哪个大
            for (register int y = 0; y < h; y++)
                max_last_col[y] = max(
                    max_this_col_from_btm[y], max_this_col_from_top[y]);
        }
    }
    cout << max_this_col_from_top[h - 1];
    return 0;
}