Grid Dynamic Programming

Grid DP extends simple path counting with obstacles and landing costs. We compute both the number of allowed right/down paths and the cheapest one. The allowed directions make the state graph acyclic, so coordinates give a dependency order. Ordinary table DP is not a general replacement for BFS or shortest-path algorithms when moves introduce cycles.

Prerequisites: Two-Dimensional DP; unreachable states; modular counting.

Build the idea

1. Recognize the repeated subproblems

   Many path histories meet at the same grid cell. With right/down movement, future options depend on the cell, and every predecessor lies above or left. Obstacles remove states rather than adding a time dimension. For at most 500×500 cells, a table scan is far smaller than enumerating path orders. Four-direction movement destroys this simple acyclic dependence.

2. Define the state

   ways[r][c] counts source-to-cell paths modulo 10^9+7. best[r][c] is minimum sum of all visited cell costs, including the source and destination. Input −1 marks an obstacle; other costs are nonnegative. best=INF means unreachable, independent of the modular path count, which could equal zero even when a positive exact count is a multiple of the modulus.

3. Derive the transition

   For a passable nonstart cell, sum the ways from valid above/left cells. For cost, choose the smaller finite predecessor and add the cell cost. A blocked cell keeps ways zero and best INF. Counts combine all paths, whereas minimum cost compares only optimum prefix costs; both use the same predecessor geometry with different aggregation operations.

   $$\mathrm{best}\left[r\right]\left[c\right]=\mathrm{cost}\left[r\right]\left[c\right]+\min \left(\mathrm{best}\right[r-1\left]\right[c],\mathrm{best}[r\left]\right[c-1\left]\right)$$

4. Base cases and computation order

   If the source is passable, initialize its count to one and best to its own cost. If blocked, it remains unreachable. Process row-major so above and left are ready. Test best!=INF before adding a cost. A blocked destination yields output 0 −1. A one-cell passable grid has one empty-movement route with that cell’s cost.

5. Correctness and invariant

   Induction on row+column partitions paths by their final edge. Distinct last edges give disjoint counting cases; replacing a path prefix by its cheaper counterpart preserves the final move and obstacle legality. No cyclic walk can return to a cell under these directions. If up/left moves are permitted, use graph search or a justified alternative state/linear system rather than repeatedly applying this table formula.

6. Work the example

   For costs [[1,2,3],[4, blocked,2],[1,1,1]], only two monotone paths avoid the center. Their costs are 9 around the top and 8 around the bottom. Thus print 2 8. The best-cost table shows unreachable center as INF; no transition is allowed through it.

   row / col	0	1	2
   0	1	3	6
   1	5	INF	8
   2	6	7	8

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n,m;
    std::cin>>n>>m;
    const long long INF=4000000000000000000LL,MOD=1000000007;
    std::vector<std::vector<long long>>best(n,std::vector<long long>(m,INF)),
        ways(n,std::vector<long long>(m));
    for(int r=0;r<n;++r){
        for(int c=0;c<m;++c){
            long long cost;
            std::cin>>cost;
            if(cost==-1){
                continue;
            }
            if(r==0&&c==0){
                best[r][c]=cost;
                ways[r][c]=1;
                continue;
            }
            if(r){
                best[r][c]=std::min(best[r][c],best[r-1][c]);
                ways[r][c]+=ways[r-1][c];
            }
            if(c){
                best[r][c]=std::min(best[r][c],best[r][c-1]);
                ways[r][c]+=ways[r][c-1];
            }
            ways[r][c]%=MOD;
            if(best[r][c]!=INF){
                best[r][c]+=cost; // Never add to the unreachable sentinel.
            }
        }
    }
    std::cout<<ways[n-1][m-1]<<' '<<(best[n-1][m-1]==INF?-1:best[n-1][m-1])<<'\n';
}

Complexity analysis

O(nm) states/time with constant predecessor work and O(nm) arrays. Streaming input means no separate cost matrix is stored. Rolling rows could reduce DP memory to O(m). Path cost≤(n+m−1)·10^9<10^12 fits long long.

Example input and output

Read n m (1..500), then n×m entries: −1 for obstacles, otherwise cost in 0..10^9. Move only right/down from top-left to bottom-right. Print path count modulo 10^9+7 and minimum inclusive cell cost, or 0 −1 if unreachable.

Input

3 3
1 2 3
4 -1 2
1 1 1

Output

2 8

For costs [[1,2,3],[4, blocked,2],[1,1,1]], only two monotone paths avoid the center. Their costs are 9 around the top and 8 around the bottom. Thus print 2 8. The best-cost table shows unreachable center as INF; no transition is allowed through it.

Practical applications

Use for acyclic grid movement, weighted monotone routes and obstacle counts. BFS handles unweighted cyclic movement; Dijkstra handles nonnegative weighted general movement. The grid coordinates alone do not make every movement problem a simple DP.

Check your understanding

Why does a zero modular path count not always prove unreachability?

Put it into practice

Enumerate all right/down routes in a small blocked grid.