Module: BFS - پیاده روی عرض


Problem

4 /6


مسیر

Theory Click to read/hide

برای بازیابی کوتاه ترین مسیرها، آرایه ای از "اجداد" \(p[]\) ایجاد کنید. ، که در آن، برای هر رأس، تعداد رأسی که با آن به این راس برخورد کرده ایم، ذخیره می شود.

Problem

در یک نمودار بدون جهت، باید حداقل مسیر را بین دو راس پیدا کنید. 
 
ورودی: 
- خط اول حاوی عدد N است - تعداد رئوس در نمودار (\(1<=N<=100\) )؛
- خطوط بعدی ماتریس مجاورت را تنظیم می کند (0 به معنای بدون لبه است، 1 - لبه)؛
- خط آخر شامل اعداد دو رأس - ابتدایی و نهایی است.
 
خروجی: ابتدا چاپ L - طول مسیر (تعداد لبه‌ها به گذر). سپس چاپ کنید عدد L+1 - رئوس به ترتیب در طول این مسیر. اگر مسیر وجود ندارد، یک عدد -1 را چاپ کنید.

مثال‌ها
<سر> <بدن>
# ورودی خروجی
1
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
 3
3 2 1 5

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!