Həbsxananı sındırmaq
Johnun missiyası iki nəfəri həbsxanadan qaçırmaqdır. Həbsxana bir mərtəbəli binadır və John bütün divar və qapıların göstərildiyi ətraflı mərtəbə planını əldə edib. O, həmçinin azad etməli olduğu iki nəfərin yerini də bilir. Həbsxana mühafizəçiləri problem deyil, çünki John onları demək olar ki, görünməz şəkildə binanı tərk etməyə məcbur edən bir yayındırma planı hazırlayıb.
Qapılar onun əsas problemidir. Bütün qapılar adətən dispetçer otağından uzaqdan açılır, lakin John onları digər vasitələrlə aça bilər. Qapını açmağa müvəffəq olduqdan sonra, onlar açıq qalır. Lakin qapıların açılması çox vaxt aparır. Buna görə də o, açmalı olduğu qapıların sayını minimuma endirmək istəyir. Johnun iki məhbusun yanına çatmaq üçün optimal marşrutu planlaşdırmasına kömək edə bilərsinizmi?
Giriş məlumatları
Birinci sətir testlərin sayını göstərir, 100-dən çox deyil. Hər bir test aşağıdakıları ehtiva edir:
bir sətir iki ədəd h və w (2 ≤ h, w ≤ 100) ehtiva edir: xəritənin eni və hündürlüyü.
sətir simvollarla, həbsxana binasını təsvir edir:
'' boş yer.
'' keçilməz divar.
'#' qapı.
'$' azad edilməli olan iki nəfərdən biri.
John binanın xarici tərəfində sərbəst hərəkət edə bilər. Xəritədə dəqiq iki nəfər var. Hər bir məhbusun yanına həbsxananın xarici tərəfindən bir yol mövcuddur.
Çıxış məlumatları
Hər bir test üçün ayrı sətirdə Johnun hər iki məhbusu azad etmək üçün açmalı olduğu ən az qapı sayını çıxarın.