المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۴:عملی:سوال ۷

بازگشت رضازاده

بعد از موفقیت غرورآفرین دلاور مردی از خطه‌ی سرسبز اردبیل،«حسین رضازاده»، مربیان او قصد دارند او را به کشور برگردانند. از آن‌جایی که در زمان رفتن به آتن فکری برای بازگشت او به ایران نکرده‌اند و در حال حاضر رضازاده فقط و فقط ویزای آتن را دارد. به علت عدم رزرو بلیط هواپیما امکان استفاده او از پرواز وجود ندارد و باید از مرزهای زمینی استفاده کند.

از آن‌جایی که مدال طلا گرفته می‌خواهد در زودترین زمان به وطن بازگردد. در نتیجه در آتن جلسه‌ای با حضور مربیان ارشد تیم تشکیل شد تا برای پیدا کردن زود‌ترین زمان ممکن راهی پیدا کنند. در جلسه‌ی مذکور به این نتیجه رسیدند که تنها عمل وقت‌گیر گرفتن ویزا می‌باشد. در نتیجه می‌خواهند مسیری پیدا کنند که از کم‌ترین تعداد کشور بگذرد. از آن‌جایی که وزنه‌برداران وقت فکر کردن به این قبیل مسائل را ندارند، تصمیم گرفتند با مسئول دوره‌ی المپیاد کامپیوتر تماس گرفته و از او کمک بجویند.

در نتیجه ما دیدیم یک ساعت پیش به موبایل محمدحسین زنگ زدند و مسئله را با او در میان گذاشتند. از آن‌جایی که محمدحسین خوابش می‌آمد به ما گفت که حل این سوال را به شما بسپاریم.

ورودی

در فایل ورودی نقشه‌ی دنیا به زبان وزنه‌بردارها آمده است. هر کشوری رنگ مخصوص به خود را دارد در ضمن رنگ هر دو کشور مجاور متفاوت است. نقشه به صورت یک جدول $m \times n$ داده شده است. هر خانه‌‌ی جدول به رنگ کشوری است که این خانه متعلق به آن کشور است. ممکن است دو کشور غیر مجاور هم‌رنگ باشند.

در سطر اول ورودی $m$ (تعداد سطرها)، سپس $n$ (تعداد ستون‌ها) آمده است. سپس چهار عدد $r_{athenas}$ (سطری که شهر آتن در آن قرار دارد) و $c_{athenas}$ (ستونی که شهر آتن در آن قرار دارد) و $r_{Ardebil}$ (سطری که شهر اردبیل در آن قرار دارد) و $c_{Ardebil}$ (ستونی که شهر اردبیل در آن قرار دارد)‌ آمده است. در $m$ سطر بعدی در هر سطر $n$‌عدد که رنگ آن خانه از جدول می‌باشد آمده است.($1 \leq m,n \leq 1000$)

خروجی

در سطر اول این فایل تعداد کم‌ترین کشورهایی که رضازاده باید از آن عبور کند (یونان و ایران را نشمارید) را بنویسید. در سطر بعدی به ترتیب رنگ کشورهایی که در راه حل شما رضازاده باید از آن‌ها عبور کند را بنویسید( ایران و یونان را به حساب بیاورید).

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3 4
1 1 2 4
1 0 1 2
0 1 2 3
0 0 1 1
2
1 0 1 3

ابزار صفحه