Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×
Grid's paths, River crossing pawn, and avoiding Knight's move, start to end count
Difference between en7 and en8, changed 970 character(s)
mMy attemt using Monte Carlo, effective when the number is small, but will resulting in REWA when dealing with larger numbers.The advantage lies in its simplicity in maths logic, while the disadvantage leadsto repetitive attemps in same paths;↵
↵
You can view the full, well-formatted C++ source code 
of Monte Carlo method here on GitHub:↵
↵
https://github.com/yawn-lento/yawns-s-codes/blob/main/P10002%E8%92%99%E5%A1%94%E5%8D%A1%E7%BD%97%E9%9A%8F%E6%9C%BA-Monte%20Carlo.cpp↵
↵
As for DFS, using iteration and recursion does make a crucial difference: we no longer waste our time on same paths, instead memory mechanism is introduced. However, we still have to try every single paths when the number grows exponentially, ending up in TLE.↵
↵
You can view the full, well-formatted C++ source code of DFS method here on GitHub:↵
↵
https://github.com/yawn-lento/yawn-s-codes/blob/main/P1002-DFS
%E5%B0%9D%E8%AF%95.cpp;↵
↵
suggestions :using DP will always be better.Finally we come to the DP method. Focusing only on results using iteration and recursion, the calculation complicity is dramatically reduced, with the only cost of not knowing the exactly how a specific path looks like.↵
↵
You can view the full, well-formatted C++ source code of DP method here on GitHub:↵
↵
https://github.com/yawn-lento/yawn-s-codes/blob/main/P1002-DP.cpp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English yawn_lento 2026-07-22 05:33:52 33 Tiny change: 'introduced. However,' -> 'introduced(though still not very effective). However,'
en8 English yawn_lento 2026-07-22 05:23:58 970
en7 English yawn_lento 2026-07-21 05:10:51 12
en6 English yawn_lento 2026-07-21 05:09:09 82
en5 English yawn_lento 2026-07-21 05:05:33 1583
en4 English yawn_lento 2026-07-21 05:01:28 42
en3 English yawn_lento 2026-07-21 04:55:47 22
en2 English yawn_lento 2026-07-21 04:53:13 26
en1 English yawn_lento 2026-07-21 04:51:02 1725 Initial revision (published)