समस्या
एक ग्रिड के ऊपर-बाएँ कोने से शुरू करें जिसमें rows x columns कोशिकाएँ हैं। केवल कोशिकाओं के किनारों के साथ चलें, हर बार एक किनारा दाएँ या एक किनारा नीचे जाएँ, जब तक कि आप नीचे-दाएँ कोने तक न पहुँच जाएँ। अलग-अलग चाल अनुक्रमों की गिनती करें। ग्रिड में कोई बाधा नहीं है।
2 पंक्तियों और 3 स्तंभों वाली ग्रिड में ठीक 2 नीचे और 3 दाएँ चालें चाहिए।
lattice_paths(rows, columns) को लागू करें।
इनपुट
rows: कोशिकाओं की पंक्तियों की संख्या, वर्टेक्स की नहीं।
columns: कोशिकाओं के स्तंभों की संख्या, वर्टेक्स की नहीं।
आउटपुट
कोने से कोने तक के रास्तों की संख्या लौटाएँ।
सीमाएँ
0 ≤ rows, columns ≤ 30 और rows + columns ≤ 60। किसी एक आयाम में शून्य होने पर सीधा रास्ता मिलता है। 0 × 0 ग्रिड में एक खाली रास्ता होता है। गिनती signed 64-bit में समा जाती है।
उदाहरण
इनपुट:
rows = 2
columns = 3
अपेक्षित आउटपुट:
expected = 10इनपुट:
long long rows = 2;
long long columns = 3;
अपेक्षित आउटपुट:
long long expected = 10;इनपुट:
long rows = 2;
long columns = 3;
अपेक्षित आउटपुट:
long expected = 10;व्याख्या
हर रास्ते में पाँच चालें होती हैं। इनमें से कौन सी दो नीचे की हैं, यह चुनने के 10 अलग-अलग तरीके हैं।
इनपुट:
rows = 0
columns = 4
अपेक्षित आउटपुट:
expected = 1इनपुट:
long long rows = 0;
long long columns = 4;
अपेक्षित आउटपुट:
long long expected = 1;इनपुट:
long rows = 0;
long columns = 4;
अपेक्षित आउटपुट:
long expected = 1;व्याख्या
केवल चार दाएँ चालों वाला सीधा रास्ता ही संभव है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर route बस जरूरी down और right moves की एक ordering है।
संकेत 2
Paths को one by one explore करने के बजाय, सभी moves में से एक move type की positions चुनने के तरीके count करो।
संकेत 3
Degenerate grids पर ध्यान दो: अगर एक dimension zero है, तो exactly one straight route है, और 0×0 grid में भी एक empty route होता है।
अपेक्षित जटिलता
समय O(min(rows, columns)), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।