enter image description here

From the upper left square, lay such a path to the lower right square so that the sum of the numbers written in the intermediate squares, as well as in the starting and finishing squares, is 110 once).

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

The problem is that I cannot understand how and where to return if the amount at the end of the journey or earlier is incorrect. How to understand after which element the wrong path was chosen.

  • The most reliable way out of the maze - go all the way) That is, you go back one step and make another turn. Well, or two steps, if there was no fork - Matty
  • @Matty I understand this, but I can not implement software. - LionQ

1 answer 1

Here, having fun ... http://ideone.com/DSMlQs
Such a recursive search with clipping.

 #include <iostream> #include <iomanip> 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); }