CCC '12 S5 - Mouse Journey - DMOJ: Modern Online Judge

CCC '12 S5 - Mouse Journey

Points: 7

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2012 Stage 1, Senior #5

You are a mouse that lives in a cage in a large laboratory. The laboratory is composed of one rectangular grid of square cages, with a total of $R$ ~R~ rows and $C$ ~C~ columns of cages ( $1 \le R, C \le 25$ ~1 \le R, C \le 25~).

To get your exercise, the laboratory owners allow you to move between cages. You can move between cages either by moving right between two adjacent cages in the same row, or by moving down between two adjacent cages in the same column. You cannot move diagonally, left or up.

Your cage is in one corner of the laboratory, which has the label $(1, 1)$ ~(1, 1)~ (to indicate top-most row, left-most column). You would like to visit your brother who lives in the cage labelled $(R, C)$ ~(R, C)~ (bottom-most row, right-most column), which is in the other corner diagonally. However, there are some cages which you cannot pass through, since they contain cats.

Your brother, who loves numbers, would like to know how many different paths there are between your cage and his that do not pass through any cat cage. Write a program to compute this number of cat-free paths.

Input Specification

The first line of input contains two integers $R$ ~R~ and $C$ ~C~, separated by one space representing the number of rows and columns (respectively). On the second line of input is the integer $K$ ~K~, the number of cages that contain cats. The next $K$ ~K~ lines each contain the row and column positions (in that order) for a cage that contains a cat. None of the $K$ ~K~ cat cages are repeated, and all cages are valid positions. Note also that $(1, 1)$ ~(1, 1)~ and $(R, C)$ ~(R, C)~ will not be cat cages.

Output Specification

Output the non-negative integer value representing the number of paths between your cage at position $(1, 1)$ ~(1, 1)~ and your brother's cage at position $(R, C)$ ~(R, C)~. You can assume the output will be strictly less than $1\,000\,000\,000$ ~1\,000\,000\,000~.

Sample Input 1

2 3
1
2 1

Output for Sample Input 1

Sample Input 2

Output for Sample Input 2

Comments

0

gj504772 commented on Feb. 3, 2023, 1:38 a.m.

it seems you can solve it using bfs

-21

Overseas commented on Jan. 2, 2021, 8:57 a.m. ← edited →

hint, it is a question about combination. if there are no grids are blocked, the number of path way to move from (0,0) to (R,C) would be Combination(R+C,C). so the problem is asking for you, what if there are?

This comment is hidden due to too much negative feedback. Show it anyway.

9

Evanhyd commented on Jan. 19, 2021, 2:14 a.m.

Where is your combinatorics solution then?

-11

Overseas commented on Feb. 16, 2021, 6:12 p.m.

It is achievable, the logic makes sense, but I suck at recursion and dp therefore I am not doing in that way, but if u just think it is wrong because I didn't do that. I have nothing to say....... I am just here to provide a logic to do this question. If u have studied data management, u know what I am saying

This comment is hidden due to too much negative feedback. Show it anyway.

2

Xiang_li commented on July 30, 2021, 2:07 p.m. ← edited →

You would have to look at the number of ways to get to R,C, then subtract ways to get to catr, caty * ways to get from catr, catc to r,c. But if there are more cats, you would have to use PIE, which is very complicated.

2

d commented on Nov. 17, 2021, 9:05 a.m.

I highly recommend https://dmoj.ca/problem/halfgrid to anyone who can find a combinatorics solution.

-3

YaySushi commented on Jan. 3, 2021, 4:45 a.m.

spittin' facts

-2

georgezhang006 commented on July 6, 2020, 1:52 a.m.

Um, can someone help me? I'm getting TLE in case #5 and #7.

Thanks!

3

c commented on July 6, 2020, 5:49 a.m. ← edit 2 →

Join the DMOJ Discord for help.

0

nabil_boudraa38 commented on Aug. 27, 2019, 9:26 p.m.

why am I getting WC in 3 cases?

8
hxxr commented on Aug. 28, 2019, 4:41 a.m.
Be careful! Your code is checking negative array indices in one of its loops. Be aware that because of how C/C++ arrays work some odd things happen when you index element -1 in a 2-dimensional array:

#include <bits/stdc++.h> using namespace std; int main(){ int a[100][100] = {0}; a[0][99] = 1234; cout << a[1][-1]; return 0; }

You get 1234 as output because a[0][99] and a[1][-1] are technically accessing the same position in memory.

In summary, avoid negative index values. Make your array longer by 1 in both dimensions and adjust the variables in your loops.

6

nabil_boudraa38 commented on Aug. 29, 2019, 11:30 a.m.

Thank you so much. Your comment was very helpful.

6

Suraj_IOI commented on June 2, 2019, 4:06 p.m.

Classic DP problem.

-27

Overseas commented on Jan. 2, 2021, 9:10 a.m.

it is more likely to be a combination problem,it is a question about combination. if there are no grids are blocked, the number of path way to move from (0,0) to (R,C) would be Combination(R+C,C). so the problem is asking for you, what if there are?

This comment is hidden due to too much negative feedback. Show it anyway.

6

vichua2006 commented on Feb. 12, 2021, 3:23 p.m.

i.e. a dp question

-1

31501357 commented on April 14, 2019, 4:15 p.m.

What if R,C=1,1?

4

bloxblox commented on Jan. 18, 2019, 12:24 p.m.

I submitted literally the exact same code onto wcipeg and got AC. Anyone know why this happened?

7

kingW3 commented on Jan. 18, 2019, 2:57 p.m.

You're checking if if (arr[i][j] != -1) but arr[i][j] might not be initialized and hence might equal -1, this migth work on wcipeg because the "random values" aren't $-1$ ~-1~, or because the compiler initialized the array to $0$ ~0~, or perhaps something entirely different the compiler pretty much has freedom to do whatever it wants if it gets undefined behaviour.

3

bloxblox commented on Jan. 23, 2019, 1:52 a.m.

got it now, thanks!