Recently ,I faced a question which says that given a square matrix of size n x n with entries only as 0 ans 1's ,we are required to count the number of unique paths from (1,1) to (n,n) if "0" means that the cell is safe and "1" means that there is an obstacle. We are allowed to move in four directions if possible that is from (X,Y), one can move to (X,Y+1), (X,Y-1),(X+1,Y) or (X-1,Y). Each cell can be visited at most once. I tried to solve it with dyanamic programming , but couldn't make my way to AC. One thing more, N<=20. Can anyone give me some hint how to solve this?
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/22/2024 20:58:44 (h1).
Desktop version, switch to mobile version.
Supported by
I think it's will help you
I just wanted to know what if N<=100000 and the obstacles are less than 3000. How do you solve the problem then? I knew there is a method to iterate only on the obstacles but I forgot that method. Can anyone help?
If the moves were only down and right, then this is the problem: https://codeforces.net/contest/559/problem/C
The method can be seen in the editorial.