কতগুলি পথ? ( Count the Way )

রাদ একটি দ্বিমাত্রিক গ্রিডে বাস করে। তার বাসা গ্রিডের (1,1) ব্লকে (গ্রিডের সবচেয়ে নীচের বামের ব্লকটি) এবং তার স্কুল গ্রিডের (N,M) ব্লকে। রাদ বাসা থেকে স্কুলে যেতে চায়, কিন্তু কতগুলি ভিন্ন ভিন্ন পথে বাসা থেকে স্কুলে যাওয়া যায়, রাদ তা জানে না। কারণ তার মা বলেছে, “রাদ, তুমি শুধু ডানদিকে এবং উপরের দিকে যেতে পারবে এবং তুমি কোন অন্ধকার ব্লকে যাবে না।” রাদ তার মায়ের কথা মেনে নেয় এবং সে স্কুলে যাওয়ার পথে তার বন্ধু অনি কেও সাথে নিতে চায়। অনি গ্রিডের (X,Y) ব্লকে থাকে। বাসা, স্কুল বা অনি কোনটিই অন্ধকার ব্লকে অবস্থিত নয়।

তুমি রাদকে সাহায্য করতে চাও। সুতরাং, তোমার কাজ হল রাদ (1,1) ব্লক হতে (N,M) ব্লকে কতগুলি পথে যেতে পারে তা নির্ণয় করা, যাতে পথগুলি (X,Y) ব্লক দিয়ে যায় এবং কোন অন্ধকার ব্লক দিয়ে না যায়। মনে রাখবে যে রাদ কোন একটি ব্লক হতে শুধুমাত্র এর ডানদিকের অথবা উপরের দিকের ব্লকে যেতে পারে।

ইনপুটের বর্ণনা

ইনপুটের প্রথম লাইনে টেস্টকেসের সংখ্যা T দেওয়া থাকবে। এর পরে T (1 <= T <= 20) টি টেস্টকেসের বর্ণনা থাকবে। প্রতিটি টেস্টকেসের প্রথম লাইনে স্পেস দিয়ে আলাদা করা দুইটি ধনাত্মক পূর্ণসংখ্যা N ও M দেওয়া থাকবে (1 <= N, M <= 50) , যা স্কুলের অবস্থান নির্দেশ করে। পরবর্তী লাইনে স্পেস দিয়ে আলাদা করা দুইটি ধনাত্মক পূর্ণসংখ্যা X ও Y দেওয়া থাকবে, যা অনির অবস্থান নির্দেশ করে (1 <= X <= N, 1 <= Y <= M) ।

পরবর্তী লাইনে একটি অঋণাত্মক পূর্ণসংখ্যা K দেওয়া থাকবে, যা অন্ধকার ব্লকের সংখ্যা নির্দেশ করে (0 <= K <= min(50, N*M)) । পরবর্তী K লাইনের প্রত্যেকটিতে স্পেস দিয়ে আলাদা করা দুইটি ধনাত্মক পূর্ণসংখ্যা DXi ও DYi থাকবে, যেগুলি অন্ধকার ব্লকের অবস্থান নির্দেশ করে (1 <= DXi <= N, 1 <= DYi <= M)। বাসা, স্কুল বা অনি কোনটিই অন্ধকার ব্লকে অবস্থিত নয়।

অাউটপুটের বর্ণনা

প্রতিটি টেস্টকেসের জন্য একটি লাইনে একটি পূর্ণসংখ্যা X আউটপুট দিতে হবে, যেখানে X হল রাদ কতগুলি পথে বাসা থেকে স্কুলে যেতে পারে তার সংখ্যা। X সংখ্যাটি অনেক বড় হতে পারে, তাই X কে 10004 দিয়ে ভাগ করে ভাগশেষ আউটপুট দিতে হবে।

Sample

Input
2 
5 4 
4 3 
0 
5 4 
4 3 
4 
2 4 
3 3 
3 4 
5 2

**Output**
20 
8

প্রবলেমটা বিস্তারিত আছে--এই লিংকে

আমার চিন্তা ভাবনাঃ

এখানে একটি 2D array নিতে হবে বুজতে পারছি। ধরি প্রথমে সবগুলা ঘরে যাওয়া যাবে, তার জন্ন সবগুলা ঘরের জন্য ১ ধরি। তারপর যে ঘরগুলা blocked সেগুলাকে ০ করে দিব । কিন্তু আমার সমস্যা হচ্ছে এই যে স্কুলের অবস্থান আসবে ইওযার এর কাছ থেকে।তাহলে আমি কিভাবে grid এর সাইজ ধরব? আন্দাজি নিলে তো result হবে না । আমি অনেকবার try করতেছি, কিন্তু grid সাইজ নিতে পারছি না। আর আমি কিভাবে দুরত্ত মাপবো? আবার 'অনিকে' সাথে নিতে হবে। এটা কিভাবে solve করবো বুজতে পারতেছি না ।

asked 23 Mar '16, 06:11

AhadKhan's gravatar image

AhadKhan
95219


সমাধানটি গ্রাফিকালি একটু বুঝাই । আশাকরি আপনি এর কোড করতে পারবেন ।

এখানে দ্বিতীয় উদাহরণটি আমি বুঝাবো । প্রথমে গ্রিডের হিসাবটা বুঝাই । alt text

এবার বাড়ি (১,১) থেকে স্কুলের(৫,৪) যাওয়ার সম্ভাব্য পথ নির্নয় করি । এখানে প্রথমে কোনো ব্লক রাখলাম না হিসাবটা সহজে বুঝানোর জন্য ।

হিসাবটা হলো যেহেতু কোন একটি ব্লক হতে শুধুমাত্র এর ডানদিকের অথবা উপরের দিকের ব্লকে যাওয়া যাবে । তাই আমি কোনো ব্লকে (ধরিঃ ৪,২) যেতে পারব শুধুমাত্র বাম পাশের (৩,২) ও নিচের ব্লক থেকে (৪,১) ।

তার মানে

(৪,২) ব্লকে যাওয়ার সম্ভাব্য রাস্তার সংখ্যা = (৩,২) ব্লকে যাওয়ার সম্ভাব্য রাস্তার সংখ্যা + (৪,১) ব্লকে যাওয়ার সম্ভাব্য রাস্তার সংখ্যা

alt text

এবার দেখে নেই অনির বাড়ি রাস্তা আর কোথায় কোথায় ব্লক আছে alt text

প্রথমে বের করবো বাড়ি থেকে অনির বাড়ি যাওয়ার সম্ভাব্য উপায় । যেহেতু এখানে ব্লক আছে তাই যেখানে ব্লক থাকবে মানে যাওয়া যাবে না । সেখানে যাওয়ার সম্ভাব্য উপায় শূন্য । তাহলে বাড়ি থেকে অনির বাড়ি যাওয়ার সম্ভাব্য উপায় বের করে ফেলি । alt text

এখানে বাড়ি থেকে অনির বাড়ি যাওয়ার সম্ভাব্য উপায় = ৪ ।

একই ভাবে হিসাব করবো অনির বাড়ি থেকে স্কুলে যাওয়ার সম্ভাব্য উপায় ।

alt text

এখন আমরা পেলাম অনির বাড়ি থেকে স্কুলে যাওয়ার সম্ভাব্য উপায় = ২ ।

তাই নিজের বাড়ি থেকে ব্লক বাদ দিয়ে অনির বাড়ি হয়ে স্কুলে যাওয়ার সম্ভাব্য উপায় 
= আপনার বাড়ি থেকে অনির বাড়ি যাওয়ার সম্ভাব্য উপায় X অনির বাড়ি থেকে স্কুলে যাওয়ার সম্ভাব্য উপায়
= ৪ X ২
= ৮
permanent link

answered 24 Mar '16, 18:26

Sharif%20Chowdhury's gravatar image

Sharif Chowdhury
3.5k111

ভাইয়া কিছু মনে কইরেন না।আমি সম্ভাব্য ব্লক এ যাওয়ার উপায়গুলি বুজতে পারি নাই।হয়ত সহজ বিষয় টাকে বেশি পেঁচিয়ে ফেলছি।যেমন ৪,২ ব্লকে যাওয়ার সম্ভাব্য উপায়গুলি কি কি?৪,১ ও ৩,২ও২,২ ও ১,২ এই ব্লকগুলা কি? আসলে আমি বুজতে পারছি না ২ নং চিত্রটি কিভাবে এল!প্রথম থেকে সমস্যা হচ্ছে এই গ্রিড এ যাওয়ার সম্ভাব্য উপায় নিয়ে।বুজতে না পারার জন্য আমি খুব দুঃখিত।আমি প্রধান বিষয় গুলা বুজতে পেরেছি।যেমন ১,১ থেকে উপর আর বামে ছাড়া কোথাও যাওয়া যাবে না।তাই কোন ঘর যেমন৪,২থেকে বামে(৩,২)এবং নিচে (৪,১) যাওয়ার সম্ভাব্য উপায় বের করতে হবে।আবার৩,২হবে২,৩এবং৩,১ যাওয়ার সম্ভাব্য উপায়। আমি মোটcalculationবুজতে পারছি না।ভুল হলে মাফ করবেন ।

(25 Mar '16, 06:06) AhadKhan

vaiya hotse na , 2 number pic ta kivabe ashlo ektu bujiye den

(27 Mar '16, 08:41) AhadKhan

এখানে (1 <= N, M <= 50) বলে দেওয়া আছে সেক্ষেত্রে ডিক্লিয়ার করার সময় 50*50 ম্যাট্রিক্স যথেষ্ট । রিস্ক নিতে না চাইলে এর বেশি নেওয়া যায় যেমন arr[55][55] ।

আবার (1 <= X <= N, 1 <= Y <= M) ও (1 <= DXi <= N, 1 <= DYi <= M) দেওয়া আছে । তাই সকল মান শূন্য করা আর সার্চ করা সব কিছু N*M এর মধ্যে রাখলেই হবে ।

permanent link

answered 23 Mar '16, 09:53

Sharif%20Chowdhury's gravatar image

Sharif Chowdhury
3.5k111

Thankssss , solve korar try kortesi !!

(23 Mar '16, 09:59) AhadKhan

ভাইয়া ,অনেক ট্রাই করলাম। আমার সমস্যাগুলি :

আমি ৫৫*৫৫ গ্রিড নিলাম। কিন্তু স্কুলের অবস্থান (N,M) আসবে user কাছ থেকে। তাহলে আমি সব ঘর শূন্য করার জন্য বা সার্চ করার জন্য কত পর্যন্ত লুপ চালাবো ?? আর অনির অবস্থান জেনে কি লাভ হতছে? আমার তো সকল possible way বের করতে হবে।

আমি যে পর্যন্ত করেছি তা এই লিঙ্কে

(23 Mar '16, 13:13) AhadKhan

আপনি প্রথমে ব্লক বাদ দিয়ে চেষ্টা করেন । মাঝখানে অনির বাড়ি বাদ দিয়ে অর্থাৎ আপনার বাড়ি থেকে স্কুলে যাওয়ার সম্ভাব্য উপায় ।

এটি করতে পারলে তারপর চেষ্টা করেন ব্লক থাকলে কিভাবে আপনি আপনার বাড়ি থেকে স্কুলে যাবেন ।

একবার যদি আপনি ব্লক সহ আপনার বাড়ি থেকে স্কুলে জেতে পারেন তবে আপনি নিচের দুইটি হিসাব করতে পারবেন ।

আপনার বাড়ি থেকে অনির বাড়ি যাওয়ার সম্ভাব্য উপায় ।
অনির বাড়ি থেকে স্কুলে যাওয়ার সম্ভাব্য উপায় ।

আর তাহলেই হিসাব শেষ । কারন রেজাল্ট হবে

আপনার বাড়ি থেকে অনির বাড়ি যাওয়ার সম্ভাব্য উপায় X অনির বাড়ি থেকে স্কুলে যাওয়ার সম্ভাব্য উপায়
permanent link

answered 23 Mar '16, 18:12

Sharif%20Chowdhury's gravatar image

Sharif Chowdhury
3.5k111

না ভাইয়া পারলাম না , স্কুলের অবস্থান নিয়ে সমস্যায় আছি । আপনি একটু কোড সহ বুঝিয়ে দেন ।ভাইয়া মনে করেন না যে আমি সব প্রবলেম বুজে নিতেছি। কোডমারশাল এর অনেক(maximum) গুলা solve করেছি ,যেগুলা চেষ্টার পরে ও পারতেছি না সেগুলার জন্য আপনার কাছে হেল্প চাইতেছি .আমি একদম নতুন।আপনি হেল্প করাতে অনেক শিখতে পেরেছি এবং অই ধরনের অনেক সমস্যা সমাধান করেছি। আশা করি আপনি প্রতিবারের মতই হেল্প করবেন । আপনাকে thanks দিয়ে শেষ করতে পারবো না ।

(24 Mar '16, 08:44) AhadKhan

(১,১) থেকে ( ৪,২ ) যাওয়ার রাস্তা ৪ হওয়ার কারন

alt text

permanent link

answered 27 Mar '16, 13:38

Sharif%20Chowdhury's gravatar image

Sharif Chowdhury
3.5k111

এটা কোড এ রূপ দিব কিভাবে ?

(27 Mar '16, 14:35) AhadKhan
(27 Mar '16, 15:36) Sharif Chowdhury

Nice ! Onek valo laglo! Apni ei problem ta niye ekti tutorial baniye felte paren ! Khup opokar hobe amader

(27 Mar '16, 16:53) AhadKhan

ভাইয়া , আপনি এখানে যে টেকনিক ব্যাবহার করেছেন এ সম্পর্কে জানতে চাই । 2d array স্টাইল টা সম্পর্কে জানতে চাই। ভাল resource দিলে খুব ভাল হত!

(03 Apr '16, 06:41) AhadKhan

ভাইয়া আপনি এখানে যেভাবে সল্ভ করেছেন সেটা জানতে চাই । এর জন্য ভাল resource দিলে খূব ভাল হত ।

(03 Apr '16, 06:44) AhadKhan
1

Nice brother, I have solved it after a lot of hard work! First I did not understand anything ! But I didn't give up.After couple of days now I 100% know what is happening in code.I have solved another (this kind of problem).Thank you very much for helping me.

(03 Apr '16, 19:12) AhadKhan
showing 5 of 7 show 2 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×212
×90
×70
×54
×5

question asked: 23 Mar '16, 06:11

question was seen: 1,331 times

last updated: 03 Apr '16, 19:12