问题 1122 --简单dp——棋盘

1122: 简单dp——棋盘★★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 85  解决: 32
[提交][状态][命题人:]

题目描述

小明遇到了一个奇怪的棋盘,棋盘的左上角与左下角各有一枚棋子,棋盘边缘写着游戏规则,玩家每次只能控制两枚棋子走一格,左上角的棋子只能向下或向右走,到右下角停止,左下角的棋子只能向上或向右走,到右上角停止(两枚棋子必须在某一格子进行一次会面,进行某种交谈)。棋盘的每个格子放着一些金币,当棋子路过时可以收集,但两者见面的格子的金币不能动。当两枚棋子都到达目的地时,棋子所拥有的金币就会奖励给小明,求小明做多能拿多少金币?

输入

每次输入一组数据,第一行包含两个数n,m代表棋盘的大小(3<=n,m<=1000),接下来n行,每行包含m个数,代表每个格子的金币数mp[i][j](0<=mp[i][j]<=1000);

输出

输出答案
样例输入
Copy
3 3
3 4 5
6 7 8
9 4 3
样例输出
Copy
42

提示

样例中左上角的棋子(1,1)->(1,2)->(2,2)->(3,2)->(3,3)

         左下角的棋子(3,1)->(2,1)->(2,2)->(2,3)->(1,3)

         拿到的总金币数为42.

来源

 

[提交][状态]