101 - Domino

لینک سوال

مفهوم سوال

سوال یه سری دومینو به ما میده و می خواد همه ی اونها رو طوری پشت سر هم بچینیم که عدد های مجاور در دومینو ها برابر باشه .

دومینو یک قطعه مستطیل شکل با ابعاد 2*1 فرض شده که روش 2 عدد بین 0 تا 6 نوشته شده .

ترتیب و جهت اصلی دومینو هارو داریم . همچنین می تونیم یه دومینو رو برعکس کنیم و بعد ازش استفاده کنیم .

به عنوان خروجی ترتیب و جهت نهایی دومینو ها یا No Solution رو از ما می خواد .

حل :

برای حل یه گراف می سازیم که رئوس اون عدد های 0 تا 6 هستند .

به ازای هر دومینو به فرم (x,y) که تو ورودی میده ، یه یال (بدون جهت) بین x و y قرار میدیم .

با کمی دقت میشه فهمید که اگر این گراف دور(مسیر) اویلری داشته باشه ، میشه این کار رو کرد .

سوال از ما ترتیب قرار گیری نهایی دومینو هارو هم می خواد ، برای همین بعد از بدست آوردن دور(مسیر) اویلری گراف ، باید تمام یال های مسیر رو چک کنیم و به ترتیب نمایش بدیم .

برای هر یال مثل (x,y) روی مسیر یا (x,y) تو ورودی بوده یا (y,x) .