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);
}
