Skip to content

123 — Grid Movement Math

এই problem-টা একটা সুন্দর পূর্ণবৃত্ত — একদম শুরুর 001 (Even or Odd)-এ শেখা parity এখানে গ্রিডে ফিরে আসে! "ঠিক s ধাপে একটা ঘরে পৌঁছানো যায় কি?" — এই প্রশ্নের উত্তর কোনো জটিল search নয়, শুধু একটা parity (জোড়/বিজোড়) চেক। চেকার বোর্ডের সাদা-কালো ঘরের কথা ভাবলেই ব্যাপারটা চোখে দেখা যায়। Geometry-তে মনে রেখো: ছবি না এঁকে code লেখা নিষেধ — তাই ASCII গ্রিডগুলো মন দিয়ে দেখো।

Source

  • Original source: Classic exercise (grid reachability / parity)
  • Platform: — (classic competitive programming exercise)
  • Topic: Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
  • Difficulty: Medium
  • Pattern: parity reachability (জোড়/বিজোড় দিয়ে পৌঁছানো সম্ভব কিনা)
  • Basic idea inherited from: 001 — Even or Odd

1. Problem in simple words

একটা অসীম গ্রিডে তুমি শুরুতে (0, 0)-তে দাঁড়িয়ে। প্রতি ধাপে চার দিকের যেকোনো একটায় এক ঘর সরতে পারো — উপরে, নিচে, বাঁয়ে বা ডানে (কোনাকুনি নয়)। প্রশ্ন:

ঠিক sটা ধাপে (এক ধাপও কম নয়, বেশিও নয়) তুমি কি (x, y) ঘরে পৌঁছাতে পারো?

লক্ষ করো — "ঠিক s ধাপে" শব্দটা গুরুত্বপূর্ণ। শুধু পৌঁছানো নয়, ঠিক ততগুলো ধাপ ব্যবহার করতে হবে। যেমন (2, 0)-তে সরাসরি 2 ধাপে যাওয়া যায়; কিন্তু 3 ধাপে? আর 4 ধাপে?

উদাহরণ: target (2, 1)। সবচেয়ে কম ধাপ লাগে |2| + |1| = 3। তাই 3 ধাপে যায় (যেমন ডান, ডান, উপর)। 4 ধাপে যায় না (নিচে দেখব কেন)। 5 ধাপে আবার যায় (3 ধাপে গিয়ে, তারপর এক ঘর এদিক-ওদিক করে ফিরে এসে 2 ধাপ "নষ্ট")।

2. What is the math idea?

মূল গাণিতিক সত্য দুটো শর্তে ধরা। ধরো d = |x| + |y| (Manhattan distance, ন্যূনতম প্রয়োজনীয় ধাপ)। তাহলে ঠিক s ধাপে (x, y) পৌঁছানো যায় যদি এবং কেবল যদি:

  1. s >= d — অন্তত d ধাপ তো লাগবেই (এর কমে অসম্ভব), আর
  2. (s − d) জোড় (even) — বাড়তি ধাপগুলো জোড়ায় জোড়ায় "নষ্ট" করতে হয়।

দ্বিতীয় শর্তটাই আসল গণিত — parity। কেন বাড়তি ধাপ জোড় হতে হবে? প্রতিটা ধাপে x + y-এর জোড়/বিজোড়তা (parity) উল্টে যায় (এক ঘর সরলে x বা y-এর একটা ±1 বদলায়, তাই যোগফলের parity flip)। শুরুতে (0,0)-এ x + y = 0 (জোড়)। তাই s ধাপ পরে আমার parity হবে s-এর parity। target-এ পৌঁছাতে হলে target-এর parity ((x + y) mod 2) আর s-এর parity মিলতে হবে — যা ঠিক (s − d) জোড় হওয়ার সমান (কারণ d = |x|+|y| আর x+y-এর parity এক)।

3. Which basic idea does this inherit from?

এটা সরাসরি দাঁড়িয়ে আছে একদম শুরুর 001 — Even or Odd-এর উপর — গোটা repo-র প্রথম problem! 001-এ তুমি শিখেছিলে % 2 দিয়ে parity (জোড়/বিজোড়) বোঝা, আর "প্রতি ধাপে কিছু একটা উল্টে যায়" ধরনের চিন্তা। এখানে সেই parity-ই গ্রিডে রূপ নিয়েছে: প্রতিটা চলন x + y-এর parity উল্টে দেয়, ঠিক যেমন একটা সংখ্যায় 1 যোগ করলে even ↔ odd উল্টায়।

নতুন যেটা যোগ হলো — parity-কে একটা পৌঁছানোর শর্ত (reachability invariant) হিসেবে ব্যবহার করা, আর সেটাকে গ্রিড/চেকার-বোর্ডের রঙের সাথে যুক্ত করা। এই "প্রতি move-এ একটা পরিমাণ flip হয়, তাই parity একটা invariant" চিন্তাটা গ্রিড-BFS, game theory, graph 2-coloring-এ বারবার ফিরবে। তাই 001-এর ছোট্ট % 2 এখানে একটা শক্তিশালী হাতিয়ার হয়ে দাঁড়াল — শিকড়ে ফেরার দারুণ উদাহরণ।

4. Real-life analogy

ভাবো একটা দাবার/চেকার বোর্ড — সাদা আর কালো ঘর পালা করে সাজানো। তুমি একটা ঘরে দাঁড়িয়ে, আর প্রতি চালে পাশের ঘরে (উপর/নিচ/বাঁ/ডান) যাও। লক্ষ করো — প্রতিবার তুমি ঘরের রঙ বদলাও: সাদা থেকে কালো, কালো থেকে সাদা। এক চালে কখনো একই রঙে থাকতে পারো না।

তাই শুরুর ঘর যদি সাদা হয়, তাহলে 1 চাল পরে তুমি অবশ্যই কালোয়, 2 চাল পরে আবার সাদায়, 3 চালে কালোয় — অর্থাৎ চালের সংখ্যা জোড় হলে শুরুর রঙে, বিজোড় হলে উল্টো রঙে। এখন target ঘরটা যদি কালো হয়, আর তুমি সাদা থেকে শুরু করো, তাহলে শুধু বিজোড় সংখ্যক চালেই সেখানে থাকা সম্ভব — জোড় চালে কখনো নয়, যত বড় সংখ্যাই হোক। এই "রঙ মেলে কিনা" = parity মেলে কিনা। আর অবশ্যই, target যত দূরেই হোক, অন্তত সরাসরি দূরত্বটুকু চাল তো লাগবেই।

5. Visual explanation

প্রথমে চেকার-বোর্ডের parity — প্রতি ঘরে (x + y) % 2, সাদা/কালো:

গ্রিডে (x+y) parity (0=সাদা ·, 1=কালো #):

 y=2  ·  #  ·  #
 y=1  #  ·  #  ·
 y=0  ·  #  ·  #      (0,0) সাদা (·)
 y=-1 #  ·  #  ·
     x=0 1  2  3

প্রতি move রঙ বদলায় -> s চালে রঙ = s-এর parity-র সাথে মেলে

এবার target (2,1): d = |2|+|1| = 3 (কালো ঘর)। কোন s-এ পৌঁছানো যায়:

s   s>=d?  (s-d) জোড়?   পৌঁছানো যায়?
0    না        -          না
1    না        -          না
2    না        -          না   (2 < 3)
3    হ্যাঁ    0 জোড়      হ্যাঁ   <- সরাসরি: ডান,ডান,উপর
4    হ্যাঁ    1 বিজোড়    না    (parity মেলে না: 4 জোড়, target কালো)
5    হ্যাঁ    2 জোড়      হ্যাঁ   <- 3 ধাপে গিয়ে, 1 ঘর গিয়ে-ফিরে (2 নষ্ট)
6    হ্যাঁ    3 বিজোড়    না

"বাড়তি ধাপ জোড়ায় নষ্ট" কেন — এক ঘর সরে আবার ফিরে এলে 2 ধাপ লাগে, অবস্থান একই:

এক জোড়া "নষ্ট" ধাপ:   X --ডান--> Y --বাঁ--> X   (2 ধাপ, X-এই ফিরে এলাম)
তাই বাড়তি ধাপ সবসময় জোড় সংখ্যায় শোষণ করা যায়, বিজোড় নয়।

6. Example input and output

x    y    s    reachable?   কেন
-----------------------------------------------------------
2    1    3    True         d=3, s-d=0 জোড়
2    1    4    False        d=3, s-d=1 বিজোড় (parity ভুল)
2    1    5    True         d=3, s-d=2 জোড়
0    0    0    True         শুরুতেই সেখানে (d=0, s-d=0)
0    0    1    False        d=0, কিন্তু 1 ধাপে ফিরে আসা যায় না (বিজোড়)
0    0    2    True         1 ঘর গিয়ে ফিরে আসা
1    0    1    True         d=1, এক ধাপ
3    4    7    True         d=7, ঠিক সোজা পথ
3    4    6    False        s < d, অসম্ভব
-2   -3   9    True         d=5, s-d=4 জোড় (negative-ও একই নিয়ম)

মূল edge case: s = 0 (শুধু (0,0)-এই, তাও d=0 হলে), (0,0)-তে ফেরা (লাগে জোড় ধাপ — 1 ধাপে ফেরা যায় না!), আর negative coordinate (absolute নেওয়ায় নিয়ম একই)। অনেকে (0,0)-এ 1 ধাপে "থাকা যায়" ভেবে ভুল করে — যায় না, কারণ এক ধাপ সরতেই হবে।

7. Brute force thinking

সবচেয়ে সরল চিন্তা — সত্যি সত্যি সব সম্ভাব্য পথ অনুকরণ করো। ঠিক s ধাপে কোন কোন ঘরে পৌঁছানো যায়, সেই সেট বানাও ধাপে ধাপে, শেষে target আছে কিনা দেখো:

def reachable_brute(x, y, s):
    positions = {(0, 0)}
    for _ in range(s):
        nxt = set()
        for (a, b) in positions:
            for da, db in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nxt.add((a + da, b + db))
        positions = nxt
    return (x, y) in positions

এটা প্রতিটা ধাপে সম্ভাব্য ঘরের সেট বাড়ায় (একরকম BFS-by-layer), তাই নিশ্চিত ঠিক উত্তর — asserts-এ এটাই reference। ছোট s-এ চমৎকার, কিন্তু সেট দ্রুত বড় হয়।

8. Why brute force may be slow

s ধাপ পরে সম্ভাব্য ঘরের সংখ্যা প্রায় O(s²) (একটা হীরে-আকৃতির এলাকা), আর প্রতি ধাপে আগের সব ঘর থেকে নতুন ঘর বানানো — সব মিলিয়ে প্রায় O(s³) কাজ ও O(s²) স্মৃতি।

s = 100000 হলে:
  brute (set সিমুলেশন): ~s^3 ≈ 10^15 কাজ, s^2 ≈ 10^10 স্মৃতি   (সম্পূর্ণ অসম্ভব)
  parity সূত্র         : O(1) — দুটো তুলনা আর একটা % 2          (তাৎক্ষণিক)

মূল অপচয় বিশাল — আমরা প্রতিটা পথ/ঘর সিমুলেট করছি, যেখানে গণিত (দূরত্ব + parity) দুটো লাইনে উত্তর দিয়ে দেয়। আসলে "পৌঁছানো যায় কিনা" পুরো পথের উপর নির্ভর করে না, শুধু দুটো invariant-এর উপর: যথেষ্ট ধাপ আছে কি, আর parity মেলে কি।

9. Better thinking

মূল insight — পথ সিমুলেট করার দরকারই নেই; দুটো শর্ত যথেষ্ট: যথেষ্ট ধাপ (s >= d) আর parity মেলা ((s − d) জোড়):

def reachable(x, y, s):
    d = abs(x) + abs(y)            # ন্যূনতম প্রয়োজনীয় ধাপ (Manhattan)
    return s >= d and (s - d) % 2 == 0

মাত্র দুটো তুলনা আর একটা % 2 — O(1)। দূরত্ব বলে দেয় "অন্তত কত লাগবে", আর parity বলে দেয় "বাড়তিটুকু জোড়ায় নষ্ট করা যায় কিনা"। এই এক লাইন সিমুলেশনের সব কাজ মুছে দেয়।

10. Thinking tweak

আসল "আহা!" — পৌঁছানো যায় কিনা পুরো পথের উপর নির্ভর করে না; শুধু দুটো জিনিসে: (১) যথেষ্ট ধাপ আছে কি, আর (২) parity মেলে কি।

দ্বিতীয়টাই মূল মোচড়: প্রতিটা চলন x + y-এর parity উল্টে দেয় (চেকার বোর্ডের রঙ বদলানোর মতো), তাই s ধাপ পরের parity বাঁধা — s-এর সাথে মেলে। target-এর parity মিলতে হবে, আর বাড়তি ধাপ সবসময় জোড়ায় ("গিয়ে-ফিরে") শোষণ করা যায়, বিজোড়ে নয়। "ঠিক k ধাপে / move-এ পৌঁছানো/ফেরা যায় কি" দেখলেই এই দূরত্ব + parity জোড়া মাথায় আসুক — search নয়, গণিত। (001-এর % 2 এখানে গ্রিডের ভাষায় কথা বলছে।)

11. Step-by-step dry run

target (2, 1), তিনটা s মান পরীক্ষা করি:

s = 3: 1. d = |2| + |1| = 2 + 1 = 3। 2. s >= d? 3 >= 3 → হ্যাঁ। 3. (s − d) % 2 = (3 − 3) % 2 = 0 % 2 = 0 (জোড়) → হ্যাঁ। 4. দুই শর্তই সত্যি → True। (পথ: ডান, ডান, উপর।)

s = 4: 1. d = 3 (একই)। 2. s >= d? 4 >= 3 → হ্যাঁ। 3. (s − d) % 2 = (4 − 3) % 2 = 1 % 2 = 1 (বিজোড়) → না। 4. দ্বিতীয় শর্ত ব্যর্থ → False। (parity মেলে না — 4 জোড় ধাপ মানে শেষে সাদা ঘর, কিন্তু (2,1) কালো।)

s = 5: 1. d = 3; 5 >= 3 হ্যাঁ; (5 − 3) % 2 = 2 % 2 = 0 জোড় → হ্যাঁ → True। (3 ধাপে (2,1)-এ, তারপর এক ঘর উপরে-নিচে করে 2 ধাপ নষ্ট।)

তিনটাই brute force সিমুলেশনের সাথে মিলে গেল।

12. Python solution

def reachable(x, y, s):
    """(0,0) থেকে ঠিক s ধাপে (4-দিক চলন) (x,y)-তে পৌঁছানো যায় কিনা। O(1)।"""
    d = abs(x) + abs(y)               # ন্যূনতম প্রয়োজনীয় ধাপ (Manhattan)
    return s >= d and (s - d) % 2 == 0


def reachable_brute(x, y, s):
    """সব পথ স্তরে স্তরে সিমুলেট করে — reference (ছোট s)।"""
    positions = {(0, 0)}
    for _ in range(s):
        nxt = set()
        for (a, b) in positions:
            for da, db in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nxt.add((a + da, b + db))
        positions = nxt
    return (x, y) in positions


# --- হাতে বাছা test ---
assert reachable(2, 1, 3) is True       # d=3, s-d=0
assert reachable(2, 1, 4) is False      # parity ভুল
assert reachable(2, 1, 5) is True       # d=3, s-d=2
assert reachable(0, 0, 0) is True       # শুরুতেই সেখানে
assert reachable(0, 0, 1) is False      # 1 ধাপে ফেরা যায় না
assert reachable(0, 0, 2) is True       # গিয়ে-ফিরে
assert reachable(1, 0, 1) is True       # এক ধাপ
assert reachable(3, 4, 7) is True       # সোজা পথ
assert reachable(3, 4, 6) is False      # s < d
assert reachable(-2, -3, 9) is True     # negative-ও একই নিয়ম

# --- brute force-এর সাথে cross-check (random, ছোট s) ---
import random
random.seed(5)
for _ in range(3000):
    x = random.randint(-4, 4)
    y = random.randint(-4, 4)
    s = random.randint(0, 9)
    assert reachable(x, y, s) == reachable_brute(x, y, s), (x, y, s)

print(reachable(2, 1, 3))    # True
print(reachable(2, 1, 4))    # False
print("সব test pass!")

13. Line-by-line explanation

d = abs(x) + abs(y)

(0,0) থেকে (x,y)-তে ন্যূনতম কত ধাপ লাগে — Manhattan distance। কোনাকুনি চলা যায় না বলে এটাই সবচেয়ে ছোট পথ, এর কমে পৌঁছানো অসম্ভব।

return s >= d and (s - d) % 2 == 0

দুটো শর্ত একসাথে। s >= d: অন্তত d ধাপ থাকতেই হবে (নইলে দূরত্বই পেরোনো যায় না)। (s - d) % 2 == 0: বাড়তি ধাপ s − d জোড় কিনা — কারণ বাড়তি দূরত্ব শুধু "এক ঘর গিয়ে আবার ফিরে" (২ ধাপ) করে শোষণ করা যায়, বিজোড় বাড়তি ধাপ কখনো শোষণ হয় না। দুটোই সত্যি হলে ঠিক s ধাপে পৌঁছানো সম্ভব। (এটাই parity invariant — প্রতি চলন রঙ/parity উল্টায়।)

cross-check অংশে 3000টা random (x, y, s)-তে O(1) সূত্র আর স্তর-সিমুলেশন brute মিলিয়ে দেখা (negative ও (0,0) সহ) — সব মিললে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

True
False
সব test pass!

প্রথম লাইন: reachable(2,1,3) → dry run-এ পাওয়া True (d=3, s−d=0 জোড়)। দ্বিতীয়: reachable(2,1,4) → False (s−d=1 বিজোড়, parity মেলে না)। তার আগের সব assert (হাতে বাছা edge case + 3000টা random cross-check) চুপচাপ pass। সবশেষে সব test pass! — parity সূত্র প্রতিটা কেসে সিমুলেশনের সাথে মিলেছে।

15. Time complexity

O(1) — কয়েকটা absolute, একটা যোগ, একটা তুলনা আর একটা % 2। s, x, y যত বড়ই হোক কাজ বাড়ে না। (brute সিমুলেশনের O(s³)-এর তুলনায় আকাশ-পাতাল — পথ ঘোরার বদলে সরাসরি গণিত।)

16. Space complexity

O(1) — শুধু d আর কয়েকটা মান; কোনো set, array বা grid লাগছে না। (brute reference-এ সম্ভাব্য ঘরের set O(s²) জায়গা নেয়, কিন্তু আসল সমাধান ধ্রুবক।)

17. Common mistakes

  1. parity শর্ত ভুলে যাওয়া — শুধু s >= d চেক করলে ভুল; (s − d) জোড় হওয়াও লাগবেই (নইলে (2,1)-এ 4 ধাপ ভুল করে True হবে)।
  2. (0,0)-এ ফেরা ভুল ভাবা — শুরুর ঘরে 1 ধাপে থাকা যায় না (এক ধাপ সরতেই হবে); d=0 হলেও parity লাগে, তাই বিজোড় s-এ False।
  3. কোনাকুনি চলন ধরে নেওয়া — এই নিয়ম 4-দিক (Manhattan) চলনের; 8-দিক (রাজা) হলে দূরত্ব Chebyshev হয়, শর্ত বদলায়।
  4. negative coordinate ভুল — abs নিতে ভুলো না; d = |x| + |y|, x + y নয় (parity এক হলেও দূরত্ব আলাদা)।
  5. strict "ঠিক s" বনাম "≤ s" গুলিয়ে ফেলা — এখানে ঠিক s ধাপ; "অন্তত s" বা "≤ s ধাপে পৌঁছানো" হলে শর্ত আলাদা হতো (শুধু s >= d)।

18. Harder problems that inherit this idea

  • LeetCode — Reachable Nodes With Restrictions / grid BFS variants — গ্রিড-চলনে parity ও দূরত্ব invariant একই পরিবার।
  • Codeforces — Theatre Square (https://codeforces.com/problemset/problem/1/A) — গ্রিড/টালি গণিত; ceiling division-এর সরল coordinate চিন্তা।
  • LeetCode — Minimum Knight Moves (https://leetcode.com/problems/minimum-knight-moves/) — ঘোড়ার চলনে দূরত্ব ও parity দুটোই লাগে; এই চিন্তার উন্নত রূপ।

19. Pattern learned

Parity-based grid reachability — (0,0) থেকে ঠিক s ধাপে (4-দিক) (x,y) পৌঁছানো যায় ⟺ s >= |x|+|y| এবং (s − (|x|+|y|)) জোড়; কারণ প্রতি চলন x+y-এর parity উল্টায় (চেকার-বোর্ডের রঙ)। বড় শিক্ষা: "ঠিক k ধাপে পৌঁছানো যায় কি" search নয় — দূরত্ব (যথেষ্ট ধাপ?) + parity (প্রতি move-এ কী flip হয়?) দুটো invariant দিয়েই O(1)-তে উত্তর। আর parity = 001-এর % 2, শুধু গ্রিডের ভাষায়।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Grid reachability = s ≥ |x|+|y| এবং (s − d) জোড়; প্রতি 4-দিক move x+y-এর parity উল্টায় (চেকার বোর্ড), তাই বাড়তি ধাপ জোড়ায় নষ্ট হয়। Signal: 'ঠিক k ধাপে পৌঁছানো/ফেরা যায় কি' দেখলেই দূরত্ব + parity মনে পড়ুক — 001-এর %2 গ্রিডে ফিরল।"

পরের ধাপ → 124 — Pick's Theorem Intro (lattice point গণনার সুন্দর সূত্র)। ভিত্তি → 001 — Even or Odd (parity-র শিকড়)। সম্পর্কিত → 121 — Manhattan Distance Tricks।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।