| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
AMROTS2 - Ամրոց (բարդ) |
Մրցույթն առանց գրաֆների ու ծառերի մրցույթ չէ
Երիտասարդ գրաֆը ցանկանում էր ամրոց ունենալ։ Գրաֆի տրամադրության տակ է գտնվում մի անտառածածկ ուղանկյունաձև տարածք։ Գրաֆը սիրում է բնությունը և ուզում է ինչքան հնարավոր է քիչ ծառեր կտրել։ Ամրոցը նույնպես պետք է զբաղեցնի ուղանկյունաձև տարածք։ Անտառը կարել է ներկայացնել երկու չափանի զանգվածի տեսքով որտեղ կան երկու տեսակի վանդակներ՝ ծառ և դատարկ։ Ամրոցը նույնպես կարել է ներկայացնել երկու չափանի զանգվածի տեսքով որտեղ կան երկու տեսակի վանդակներ՝ քար և դատարկ։ Ամրոցը կարել է պտտեցնել և հայելային արտապատկերել։ Ամրոցը պետք է տեղադրել այնպես, որ այն ամբողջությամբ գտնվի անտառի մեջ (նույնիսկ եթե եզրերը դատարկ են)։ Երաշխավորվում է որ պատասխան գոյություն ունի։
Մուտքային տվյալներ
Առաջին տողում տրված են երկու n, m թվեր՝ անտառի տողերի և սյուների քանակները։ Հաջորդ n տողերում նկարագրված է անտառը ‘.’-ը նշանակում է բաց տեղ, ‘#’-ը ծառ։ Հաջորդ տողում տողում տրված են երկու n1, m1 թվեր՝ ամրոցի տողերի և սյուներ քանակները։ Հաջորդ n1 տողերում նկարագրված է ամրոցը ‘.’-ը նշանակում է դատարկ ‘#’-ը պատ։
Ելքային տվյալներ
Ելքում պետք է արտածել մեկ թիվ՝ մինիմալ ծառերի քանակը, որ գրաֆը ստիպված կլինի հատել։
Սահմանափակումներ
n, m, n1, m1 <= 300։
Օրինակներ
| Ավելացրեց. | Andreasyan |
| Ամսաթիվ. | 2020-12-20 |
| Ժամանակի սահմանափակումը. | 2s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3 |
| Աղբյուրը. | Դպրոցական փուլ, 2020-2021 |
RSS