Поиск пути в лабиринте

Oт верхнего левого квадрата проложите такой путь к нижнему правому квадрата, чтобы сумма чисел, записанных в промежуточных квадратах, а также в стартовом и финишном, составляла 110 (Искомый маршрут может пересекать только стороны, но не вершины промежуточных квадратов и проходить через каждый промежуточный квадрат только один раз).
int mass[7][7] = {{3,4,5,4,3,9,7}, {1,0,6,0,5,0,8}, {2,3,7,6,9,4,1}, {7,0,8,0,1,0,3}, {5,5,9,8,7,2,6}, {1,0,4,0,6,0,3}, {3,4,2,5,5,4,3}};
int a = -1, b = -1, K, M[15];
Search(0, 0, 0, M);
void Search(int I, int J, int S, int M[15]) { if(mass[I][J] == 0 && b == J) { //если элемент черный J--; I++; }
if(mass[I][J] == 0 && a == I) { I--; J++; }
M[I + J] = mass[I][J]; // запись пути a = I; b = J;
if ((I == 6 && J == 6) && (S + mass[I][J] == 110)) { //условие выхода K++; Rez(M);//вывод пути printf(" = %3d ", S + mass[I][J]); //сумма чисел return; }
if (I < 6) { Search(I+1, J, S+mass[I][J], M); }
if (J < 6) { Search(I, J+1, S + mass[I][J], M); } }
Проблема состоит в том что я не могу понять как и куда возвращаться, если сумма в конце пути или раньше неверна. Как понять, после какого элемента был выбран неверный путь.

Ответ

Вот, поразвлекался... http://ideone.com/DSMlQs Такой себе рекурсивный поиск с отсечениями.
#include #include
using namespace std;
const int Tgt = 110; const int I = Tgt;
int m[7][7]={ {3,4,5,4,3,9,7}, {1,I,6,I,5,I,8}, {2,3,7,6,9,4,1}, {7,I,8,I,1,I,3}, {5,5,9,8,7,2,6}, {1,I,4,I,6,I,3}, {3,4,2,5,5,4,3} };
bool path[7][7] = { false };
bool step(int x, int y, int sum) { sum += m[x][y]; if (sum > Tgt) return false; if (x == 6 && y == 6) { if (sum != Tgt) return false; path[x][y] = true; for(int i = 0; i < 7; ++i) { for(int j = 0; j < 7; ++j) { cout << (path[i][j] ? '*' : ' '); } cout << endl; } return true; }
path[x][y] = true;
// Up if (y > 0 && !path[x][y-1]) { if (step(x,y-1,sum)) return true; } // Dn if (y < 6 && !path[x][y+1]) { if (step(x,y+1,sum)) return true; } // Lt if (x > 0 && !path[x-1][y]) { if (step(x-1,y,sum)) return true; } // Rt if (x < 6 && !path[x+1][y]) { if (step(x+1,y,sum)) return true; } path[x][y] = false; return false; }
int main(int argc, const char * argv[]) { step(0,0,0); }