Լուծեք հանելուկը
Տրված է չափանի աղյուսակ, որի մեջ առկա են թվեր 1, 2, 3, …, 9։ Ձեզանից պահանջվում է կատարել swap (փոխանակման) գործողությունների որոշակի հաջորդականություն, որպեսզի ստացվի հետևյալ աղյուսակը:
Յուրաքանչյուր քայլի ժամանակ կարող եք փոխանակել երկու հարևան թվեր (հարևանությունը կարելի է դիտարկել ինչպես հորիզոնական, այնպես էլ ուղղահայաց ուղղություններով)։ Պարզեք, թե նվազագույնը քանի քայլ է անհրաժեշտ, որպեսզի ստացվի պահանջվող աղյուսակը:
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
Մուտք
Մուտքը պարունակում է 3 տող, և յուրաքանչյուր տողում տրված են 3 թվեր, որոնք ներկայացնում են նախնական աղյուսակը:
Ելք
Ծրագիրը պետք է արտածի պահանջվող տեսքով աղյուսակը ստանալու համար անհրաժեշտ նվազագույն քայլերի քանակը:
Օրինակներ
Մուտք | Ելք |
2 1 3
7 5 9
8 4 6 | 4 |
Constraints
Time limit: 50 seconds
Memory limit: 512 MB
Output limit: 1 MB