Програмчлал, Алгоритмд дуртай бүхэнд зориулав

Эзэн хааны алтан эдлэлийг аль болохоор олныг, аль болох цөөхөн үйлдлээр хулгайлахаар нэгэн нинжа хааны ордонд нэвтрэн оров. Хааны ордны зарим нэг нүдэнд занга бий. (дээш харсан хадаас, намаг,.. за тэгээд доошоо унагаад чад хийлгэх бүх л зүйл гээд ойлгочих).Нинжа алтан эдлэлээ цуглуулаад анх нэвтрэн орсон газраараа зугтах ёстой.
Нинжа хийж чадах хөдөлгөөн
А) 4 зүгт хөдлөх ба ямар ч тохиолдолд нэг нүд ахихад нэг үйлдэл гэж тооцно.
Б) Нэг нүд үсрэх.
В0) Дараалсан 2 нүд урагш хөдөлсөний дараа (энэ үедээ алтан эдлэл авч болохгүй) гүйж чадах ба алтан эдлэлийг авахын тулд зогсох шаардлагатай.
В1) Гүйж байхдаа 2 нүд ахихаар үсэрч чадна.
В2) Гүйж байхдаа хажуу талын тэр чигтээ ханыг дагаж хамгийн ихдээ 4 нүд ахиж чадах ба үүний дараа гүйхээ болино. Энд эхлэл, төгсгөлийг нүдийг оролцуулаад бүгд хажуу талын хана байх шаардлагатай!

Оролт
Эхний мөр эдлэлийн өндөр H, өргөн W /3 < = H < = 60, 3 < = W < = 80/
Дараагийн H мөрөнд тус тус W тэмдэгт байна.
Үүнээс цааш ижил тест байх ба H=0, W=0 үед зогсооно.

Тэмдэгтүүдийн төлөөлөх зүйл
'%' нинжагын анхны байрлал
'#' хана /Хааны ордоныг тойрсон хана заавал байна/
'.' хоосон талбар
'^' занга
'*' алтан эдлэл /Нэг ордонд хамгийн эхдээ 15 ширхэг байна/

Гаралт 
Тест болгоны хувьд авч чадах хамгийн их алтан эдлэлийн тоо, түүнд зарцуулагдах хамгийн бага үйлдлийн тоо

Жишээ оролт
6 23
#######################
#%.^.^#################
#^^^^^######^^^^^^^^^^#
#^^^...^^^^...^^*^^..*#
#^^^^^^^^^^^^^^^^^^^^^#
#######################
5 16
################
#^^^^^^^^^^^^^^#
#*..^^^.%.^^..*#
#^^#####^^^^^^^#
################
0 0
Жишээ гаралт
1 44
2 28