أقبلت الأبقار بحماس على لعبة الداما. رغم متعتها غير المحدودة فهي سيئة في نهاية اللعب وتريد مساعدتك.
لرقعة $N\times N$، $(4 \le N \le 30)$، حدد تسلسل الحركات الأمثل الذي ينهي اللعب في الدور التالي. تتحرك القطع فقط على + وتأسر بالقفز فوق قطعة الخصم، التي تزال فورًا. مثال $N=8$:
- + - + - + - + + - + - + - + - - + - K - + - + + - + - + - + - - o - o - + - + + - K - + - + - - o - + - + - + + - K - + - K -
K ملوك Bessie وo قطع الخصم. الدور التالي دائمًا لها. يقفز الملوك فوق الخصوم تباعًا بأي اتجاه قطري، مع إزالة المأسور. هنا الملك أسفل اليسار يقفز فوق القطع الثلاث كلها وينهي اللعب. الملك K المتحرك يميز بـ>K<.
- + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + - - + - K - + - + - + - K - + - + - + - K - + - + - + - K - + - + + - + - + - + - + - + - + - + - + ->K<- + - + - + - + - + - + - - o - o - + - + - o - o - + - + - + - o - + - + - + - + - + - + + - K - + - + - >K<- K - + - + - + - K - + - + - + - K ->K<- + - - o - + - + - + - + - + - + - + - + - + - + - + - + - + - + - + + ->K<- + - K - + - + - + - K - + - K - + - K - + - K - + - K -
من اليسار لليمين: الأصل، بعد الحركة 1، بعد الحركة 2، بعد الحركة 3.
مرت الحركات بهذه الخانات:
1 2 3 4 5 6 7 8 1 - + - + - + - + 2 + - + - + - + - 3 - + - K - + - + 4 + - * - + - + - 5 - o - o - + - + 6 * - K - * - + - 7 - o - + - + - + 8 + - K - + - K -
صف، عمود؛ البداية: $(8,3)$؛ الحركات: $(6,1)$، $(4,3)$، $(6,5)$.
جد تسلسل إنهاء اللعب لرقعة الإدخال $N\times N$ إن وجد (ويكون وحيدًا). توجد على الأقل قطعة ملك وقطعة خصم.
الإدخال
السطر 1: الصحيح $N$.
الأسطر $2,\ldots,N+1$: السطر $i+1$ يحتوي $N$ محارف
-أو+أوKأوoتمثل الصف $i$ من رقعة صحيحة.
الإخراج
- بدءًا من السطر 1: إن تعذر، اكتب
impossibleوحدها بسطر. وإلا كل سطر عددان صحيحان تفصلهما مسافة، مواقع ملك متتالية تحركاته تفوز باللعبة.
أمثلة
الإدخال 1
8 -+-+-+-+ +-+-+-+- -+-K-+-+ +-+-+-+- -o-o-+-+ +-K-+-+- -o-+-+-+ +-K-+-K-
الإخراج 1
8 3 6 1 4 3 6 5
مؤلف المسألة: Rob Kolstad، 2008