Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

AMROTS2 - Ամրոց (բարդ)

 Մրցույթն առանց գրաֆների ու ծառերի մրցույթ չէ

 

Երիտասարդ գրաֆը ցանկանում էր ամրոց ունենալ։ Գրաֆի տրամադրության տակ է գտնվում մի անտառածածկ ուղանկյունաձև տարածք։ Գրաֆը սիրում է բնությունը և ուզում է ինչքան հնարավոր է քիչ ծառեր կտրել։ Ամրոցը նույնպես պետք է զբաղեցնի ուղանկյունաձև տարածք։ Անտառը կարել է ներկայացնել երկու չափանի զանգվածի տեսքով որտեղ կան երկու տեսակի վանդակներ՝ ծառ և դատարկ։ Ամրոցը նույնպես կարել է ներկայացնել երկու չափանի զանգվածի տեսքով որտեղ կան երկու տեսակի վանդակներ՝ քար և դատարկ։ Ամրոցը կարել է պտտեցնել և հայելային արտապատկերել։ Ամրոցը պետք է տեղադրել այնպես, որ այն ամբողջությամբ գտնվի անտառի մեջ (նույնիսկ եթե եզրերը դատարկ են)։ Երաշխավորվում է որ պատասխան գոյություն ունի։

 

Մուտքային տվյալներ

Առաջին տողում տրված են երկու n, m թվեր՝ անտառի տողերի և սյուների քանակները։ Հաջորդ n տողերում նկարագրված է անտառը ‘.’-ը նշանակում է բաց տեղ, ‘#’-ը ծառ։ Հաջորդ տողում տողում տրված են երկու n1, m1 թվեր՝ ամրոցի տողերի և սյուներ քանակները։ Հաջորդ n1 տողերում նկարագրված է ամրոցը ‘.’-ը նշանակում է դատարկ ‘#’-ը պատ։ 

 

Ելքային տվյալներ

Ելքում պետք է արտածել մեկ թիվ՝ մինիմալ ծառերի քանակը, որ գրաֆը ստիպված կլինի հատել։

 

Սահմանափակումներ

n, m, n1, m1 <= 300։

 

Օրինակներ

 

Մուտք

Ելք

5 5

####.

####.

####.

####.

.....

5 5

#....

#....

#....

#....

#####

0

10 20

#.###.#.###.########

#.###........###.###

.##.#........##.#.##

#.#####..##..###.###

#.###..#.#.#.#.#..##

#.#.#.#...##..######

#####...#.....#.#.##

#.###.#..#....##.###

#.#.###.#.#.####.##.

#####.#.###.###.##..

8 8

###..###

########

###..###

.#....#.

.#....#.

###..###

########

###..###

10

 


Ավելացրեց.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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.