C++-এ সেলফ ক্রসিং (Self Crossing) সমস্যা

সেলফ ক্রসিং সমস্যা

একটি অ্যারে x দেওয়া আছে। আমরা (0,0) থেকে শুরু করে x[0] ইউনিট উত্তর, x[1] পশ্চিম, x[2] দক্ষিণ, x[3] পূর্ব, এভাবে কাউন্টার-ক্লকওয়াইজ দিয়ে চলতে থাকি। পথটি কখনো নিজের সাথে ক্রস করে কিনা তা O(1) একস্ট্রা স্পেসে নির্ধারণ করতে হবে।

উদাহরণ: [3,4,2,5] → true (পথটি নিজের সাথে ক্রস করে)

সমাধানের পদ্ধতি (O(1) স্পেস, এক পাস)

প্যাটTERN হলো তিন ধরনের ক্রসিং:

1. ফোর্থ লাইন ক্রসেস ফার্স্ট: x[i] >= x[i-2] && x[i-1] <= x[i-3]
2. ফিফথ লাইন মিটস ফার্স্ট: x[i-1] == x[i-3] && x[i] + x[i-4] >= x[i-2]
3. সিক্সথ লাইন ক্রসেস ফার্স্ট: x[i-2] > x[i-4] && x[i] >= x[i-2] - x[i-4] && x[i-1] >= x[i-3] - x[i-5] && x[i-1] <= x[i-3]

কোডে একই লজিক কোম্প্যাক্ট ফর্মে লেখা হয়েছে।

C++ কোড উদাহরণ

{3,4,2,5}

আউটপুট

1