Pathword Quest
आपको लोअरकेस इंग्लिश अक्षरों से भरा हुआ एक
n x n ग्रिड दिया गया है। आपका काम यह तय करना है कि क्या इस ग्रिड में ऐसा कोई सरल पथ (simple path) मौजूद है, जिसे क्रम से पढ़ने पर दिया गया स्ट्रिंग s बनता है।💡
एक सरल पथ (simple path) ग्रिड में किसी भी सेल से शुरू होता है और हर स्टेप में किसी भी मिलती-जुलती (adjacent) सेल (ऊपर, नीचे, बाएं या दाएं) की ओर बढ़ सकता है।
यह पथ किसी भी सेल पर केवल एक बार जा सकता है और ज़रूरत के मुताबिक दिशा बदलने की अनुमति होती है।
इस पथ में एक के बाद एक आने वाले अक्षरों को मिलाकर स्ट्रिंग
s बनना चाहिए।इनपुट
पहली पंक्ति में एक पूरा अंक
n (1 ≤ n ≤ 6) होगा, जो ग्रिड के आकार का प्रतिनिधित्व करता है।इसके बाद की अगली
n पंक्तियों में, हर पंक्ति में लोअरकेस इंग्लिश अक्षर होंगे, जो ग्रिड के हर सेल का अक्षर दर्शाते हैं।अंतिम पंक्ति में स्ट्रिंग
s (1 ≤ |s| ≤ 15) दी गई है, जो लोअरकेस इंग्लिश अक्षरों से बनी होती है।आउटपुट
यदि ऐसा सरल पथ मौजूद है, जो क्रम में पढ़ने पर स्ट्रिंग
s बनाता है, तो YES प्रिंट करें, अन्यथा NO प्रिंट करें।Examples
Input | Output |
3
a b e
d c f
g h i
abc | YES |
3
a b e
d c f
g h i
abce | NO |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB