Ալգորիթմներ և Տվյալների Կառուցվածքներ

Ցանցում ամենակարճ ուղի

Ենթադրենք, որ ունենք լաբիրինթ, ներկայացված r տող և c սյուն ունեցող ցանցով։ Ձեզ խնդրում են պարզել, թե որքան է մեկնարկային խցիկից (S) մինչև ավարտային խցիկ (E) տանող ամենակարճ ուղու երկարությունը:
Լաբիրինթը ներկայացված է հետևյալ կերպ.
  • Հարկ — կետանիշ (.)
  • Պատեր — շախ (#)
  • Մեկնարկային կետ — մեծատառ S
  • Ավարտային կետ — մեծատառ E
Կարող եք տեղաշարժվել երկու հարակից խցիկների միջև (ձախ, աջ, վերև, ներքև), եթե դրանք պատ չեն։
Ձեզ խնդրում են գտնել ամենակարճ ուղու երկարությունը S-ից E տանող ճանապարհի համար։

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր r և c (1 ≤ r, c ≤ 1000)։
Հաջորդ r տողերում պարունակվում են c սյուներ, որոնք նկարագրում են լաբիրինթը։ Յուրաքանչյուր խցիկ կարող է լինել հարկ (.), պատ (#), մեկնարկ (S) կամ ավարտ (E)։ Երաշխավորված է, որ ամբողջ ցանցում կա միայն մեկ S և մեկ E։

Ելք

Ծրագիրը պետք է տպի S-ից E տանող ամենակարճ ուղու երկարությունը։ Եթե S-ից E żad ուղի չկա, պետք է տպի Impossible։

Օրինակներ

Input

5 8
########
##.S....
....#.#.
#......#
...#...E
Output

7
 
 
Խորհուրդ
Ոչ միշտ է պետք նախօրոք կառուցել գրաֆ, որպեսզի կիրառեք BFS ալգորիթմը։ Երբեմն կարելի է աշխատել «անուղղակի» գրաֆերի (օր. ցանցերի) վրա և նույնպես օգտագործել BFS:
Հուշում
Ցանցը կարելի է ընկալել որպես գրաֆ, իսկ ամեն խցիկի համար պահպանել հեռավորության երկչափ զանգված, օրինակ՝ d[][], որտեղ d[i][j] ցույց է տալիս դեպի տվյալ խցիկ ամենակարճ ուղու երկարությունը մեկնարկային կետից:
 

Constraints

Time limit: 15 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue