Count Paths in Grid with Blocks
JavaScript
Hard
5 views
Problem Description
You are given a grid with 0 (free) and 1 (blocked). You can move only right or down. Count number of ways from top-left to bottom-right modulo 1000000007.
Input Format
First line: r c. Next r lines: c numbers (0/1).
Output Format
One integer ways mod 1e9+7.
Sample Test Case
Input:
3 3
0 0 0
0 1 0
0 0 0
Official Solution
const fs=require('fs');const lines=fs.readFileSync(0,'utf8').trim().split(/
?
/);if(!lines[0])process.exit(0);const [R,C]=lines[0].trim().split(/\s+/).map(Number);const MOD=1000000007n;let dp=new Array(C).fill(0n);for(let i=0;i<R;i++){const row=lines[i+1].trim().split(/\s+/).map(Number);for(let j=0;j<C;j++){if(row[j]===1){dp[j]=0n;continue;}if(i===0 && j===0){dp[j]=1n;continue;}const fromLeft=j>0?dp[j-1]:0n;const fromUp=dp[j];dp[j]=(fromLeft+fromUp)%MOD;}}process.stdout.write(String(dp[C-1]));
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!