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

#c #алгоритм

   


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


Проблема состоит в том что я не могу понять как и куда возвращаться, если сумма в
конце пути или раньше неверна. Как понять, после какого элемента был выбран неверный путь.
    

Ответы

Ответ 1

Вот, поразвлекался... 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);
}