DP605 方格采集路线

难度梯度：T4-｜训练重点：网格路径 DP 与障碍

题目描述

在 N×M 的网格中，从 (1,1) 出发只能向右或向下到 (N,M)。每个可走格有一个整数收益（可负）；障碍用 # 表示。必须经过的起点和终点保证不是障碍。求所有可行路径的最大收益，若不可达输出 IMPOSSIBLE。经过起点和终点都要计收益。

起点和终点也计入收益；不得进入障碍格。移动方向只有向右和向下，不能向上、向左或原地停留。

输入格式

第一行 N M。随后 N 行，每行 M 个记号：# 或整数。

输出格式

最大收益，或者 IMPOSSIBLE。

样例输入

2 3
1 2 #
-5 4 3

样例输出

10

样例说明

路径 1→2→4→3，收益 10。

数据范围

1≤N,M≤1000；N×M≤10^6；-10^6≤格子收益≤10^6。

子任务

30 分：N,M≤20；30 分：无障碍；40 分：无附加限制。