ग्रिड यात्रा

आपको एक n x n ग्रिड दिया गया है, और आपका कार्य इस ग्रिड के शीर्ष बाएँ कोने से लेकर सबसे नीचे दाएँ कोने तक जाने वाले सभी रास्तों को खोजना है।

इस ग्रिड में आप केवल नीचे या दाएँ दिशा में ही आगे बढ़ सकते हैं। प्रत्येक सेल ग्रिड में एक स्थान दर्शाता है, जो या तो खाली (empty) होता है या अवरुद्ध (blocked) होता है। अवरुद्ध सेल से होकर गुज़रना संभव नहीं है। आपका लक्ष्य सिर्फ नीचे या दाएँ की ओर चलते हुए, शीर्ष बाएँ कोने से नीचे दाएँ कोने तक पहुँचने वाले सभी संभावित रास्तों को ढूँढना है।

इनपुट

पहली पंक्ति में एक पूर्णांक n (1 ≤ n ≤ 10) दिया जाता है, जो ग्रिड का आकार दर्शाता है।

आउटपुट

केवल खाली सेल को ध्यान में रखते हुए, शीर्ष बाएँ कोने से नीचे दाएँ कोने तक जाने वाले सभी रास्तों को प्रिंट कीजिए। प्रत्येक रास्ता एक नई पंक्ति में दिखाया जाना चाहिए। हर रास्ते का प्रतिनिधित्व D (नीचे जाने के लिए) या R (दाएँ जाने के लिए) के क्रम से किया जाता है। आप इन रास्तों को किसी भी क्रम में प्रिंट कर सकते हैं।

उदाहरण