Есть изначальные данные: матрица X,Y;задаються стены. Сначало есть К-денег, за каждый ход надо платить А, а если ход отличаеться от предыдущего по направлению то A+B; в некоторых клеточках есть цифры, если путь проходит через клеточку то K=K+цифра.
Задача как обычно найти путь от Start до Finish и при этом потратить как можно меньше денег.

Но проблема в том что я не могу подобрать алгоритм    A* находит путь ,но не учитывает цену и бонусы
для Форда-Беллмана я не могу создать матрицу цен(минимальная стоймость от вершины до вершины) - или я просто туплю?

С самого начало я подумал что здесь точно граф, но потом начало складываться что может быть попробовать какие-нибудь алгоритмы из "Поиск Максимального Потока" или что нить из Динамического Программирования... 

Собственно у кого какие соображения? 
Буду Благодарен За Любые Идеи && Предложения    

учитывая условие 

у тебя не получится матрица смежности, т.к. стоимость перехода между каждыми двумя вершинами величина непостоянная.
какая размерность? может, поиск в глубину будет приемлимым решением?

X,Y<=10^6; 1 ≤ A ≤ 100, 1 ≤ B ≤ 100; 0 ≤ Количесто бонусов на карте  ≤ 20; 10 секунд на выполнение;
а разве DFS подойдёт? без изменений? 

уу... с таким количеством будет сложно :(

а чего бы ему не подойти? по-моему, самый универсальный(потому - потенциально самый медленный) алгоритм.
но с такими ограничениями... не знаю, скорее всего на несколько порядков дольше будет.
задачка олимпиадная, что ли?

горизонтальный обход дерева(по ширине) это DFS(Depth-first search) или BFS(Best-first_search)  ?

Добавлено через 11 минут и 5 секунд
мм DFS не прокатит потому что у меня ещё есть бонусы.. и как бы DFS найдёт мне дорогу, а рядом будет вершина с бонусом и если бы я через неё прошёл я бы потратил бы ещё чуть чуть но заработал бы много =) 

может искать все пути ? какой для этого алгоритм подошёл бы в матрице?

у тебя задача - потратить как можно меньше денег, или чтоб в конце пути осталось как можно больше?

Добавлено через 1 минуту и 9 секунд

убрать проверку на минимальность текущего пути относительно стоимости существующего полного пути. и тебе DFS станет 


Добавлено через 1 минуту и 44 секунды
текущая сумма денег может принимать отрицательные значения?

Задача: подсчитать максимальное возможное кол-во денег которое можно получить дойдя до финиша
текущая сумма - нет

хехе. а через одну и ту же клетку можно проходить несколько раз? если да, то можно тупо топтаться на клетках, дающих "деньги". до бесконечности 
зы Я не цепляюсь к условию. Просто, если найти "слабое место", можно будет обойтись простым алгоритмом и продемонстрировать смекалку.
Если надо решение именно в такой постановке(для чего?) - просто скажи.

Добавлено через 10 секунд
идей пока никаких.

не, топтаться нельзя    
тут просто тупо надо найти решение .... :/ постоновка именно такая :(

я просто жудко туплю, у меня задаються данные стены, положения старта/финиша,координаты бонусов, и цены... я не могу себе представить как это можно представить... в виде ребер или матрицы смежности, тоесть сразу можно отбросить такие алгоритмы :///  тут надо какую то волну пустить - но она не учтёт бонусы...

чем можно перебрать все возможные пути? - запущу несколько Thread`ов 4gb памяти и всё будет классно =] 

если допустим проход по одной клетке несколько раз, перебрать все возможные пути не получится - их будет бесконечно много

ну исключить вовсе или можно добавить условие, что бы не ходишь по одной и той же клете в одном и том же направлении

ну хоть как то   

Рассматривай граф, в котором вершине соответствует пара (позиция в матрице, направление по которому пришли в эту позицию). Тогда задача сведется к алгоритму Дейкстры. Правда, если, как ты говоришь, размер матрицы до 10^6 x 10^6, то решать ее Дейкстрой может быть несколько накладно (или я не правильно понял?), хотя тут можно придумать другие алгоритмы.

+1 за Дейкстру. Недавно тоже была похожая задача - алгоритм Дейкстры идеально подошел.

Дейкстра заведомо не уложится в отведенные 10 секунд. Перебирать 10^12 позиций поля за это время на современной технике нереально. Надо смотреть что-то из разряда path finding.  В общем, тут нужна херуистика, ведущая как-то к цели. Если бы не было стен, все было бы просто, а так лично мне не вполне понятно, как это делать. Знаю только, что эта область хорошо разработана программистами компьютерных игр.