Cəngavər Matç Oyunu#3787
İki cəngavər komandası var və bu komandaların müvafiq olaraq N və M cəngavəri var. Cəngavərlər öz komandalarında 1-dən N-ə və 1-dən M-ə qədər nömrələniblər. Onlar W*H ölçülü bir tapmacada tələyə düşüblər. Tapmacanın yalnız dörd çıxışı var və bunlar tapmacanın dörd küncündə yerləşir. Cəngavərlər yalnız yuxarı, aşağı, sola və sağa hərəkət edə bilərlər və bir hücrədən qonşu hücrəyə keçmək üçün lazım olan vaxt sabitdir. İki cəngavər aşağıdakı şərtləri ödəyirsə, "döyüş tərəfdaşı" yarada bilərlər:
İki cəngavər fərqli komandalardan olmalıdır.
Hər ikisi çıxışlardan birinə çata bilməlidir.
Çıxışlardan birinə çatmaq üçün lazım olan ən az vaxt eyni olmalıdır.
Beləliklə, neçə "döyüş tərəfdaşı" yarada bilərlər?
Bu əməliyyat üçün lider aşağıdakı təlimatları verir:
Hər komanda cəngavərləri tapmacadan çıxmaq üçün lazım olan ən az vaxtla yenidən nömrələyir. Beləliklə, ən az vaxt istifadə edən ID 1 alacaq və ən çox vaxt istifadə edən ID N və ya M alacaq. Əgər bəziləri eyni vaxt istifadə edirsə, onda orijinal ID-si daha aşağı olan daha aşağı ID alacaq.
Eyni komandadan seçilən cəngavərlər ardıcıl ID-yə malik olmalıdır.
"Döyüş tərəfdaşları" ID-lərə görə bir-bir formalaşdırılır. Yəni ən aşağı ID-yə malik olan digər komandadakı ən aşağı ID-yə malik olanla formalaşmalıdır və s.
Bir neçə test halı var. Hər test halının girişi aşağıdakı kimi təsvir olunur.
Birinci sətir, dörd tam ədəd N, M, W, H. (0 < N, M < 300, 10 < W, H < 50).
Sonra H sətir var, hər sətir tapmaca üçün W simvolu ilə göstərilir. '.' simvolu hücrənin boş olduğunu göstərir, hər boş hücrə sonsuz sayda cəngavər saxlaya bilər. '#' simvolu isə hücrənin maneə olduğunu və heç bir cəngavərin ora daxil ola bilməyəcəyini göstərir. Dörd künc boşdur.
Sonra N+M sətir var, hər sətir cəngavərin əvvəlcə x-cı sətirdə və y-cı sütunda olduğunu göstərən bir cüt tam ədəd (x, y) ilə verilir (0 ≤ x < H, 0 ≤ y < W).
Giriş faylın sonu ilə bitəcək.
Onların formalaşdıra biləcəyi maksimal "döyüş tərəfdaşı" sayını göstərən bir tam ədəd.
Nümunə 1