Поиск путь с помощью рекурсии

Question

Вот проблема

При условии, что у нас есть пхп квадратной доски с каждой небольшой площадью внутри содержит либо 1, либо 0. Начала в верхнем левом квадрате (0,0), найти путь к самый низкий квадрат справа (n, n), который дает самый большой номер завода, сделанный из всего квадрата, который он передает.

**Input** 
first line: n. 
the following n lines : each line contains n numbers of 0 or 1. 

**Output** 
the decimal number of the largest binary string you found. 

И вот мой код. Я использую рекурсию, чтобы найти весь путь, который перемещается в последний квадрат, и с каждым путем я генерирую двоичную строку и помещаю ее в вектор. В конце я напечатаю наибольшее число в векторе.

#include <iostream> 
#include <cmath> 
#include <queue> 
#include <string> 
#include <algorithm> 
using namespace std; 
#define rep(I,N) for(int I=0;I<(N);++I) 
int n; 
char field[100][100]; 
vector<string>bin; 
vector<int>de; 
string tmp; 

int dec(string bin) 
{ 
    int d=0; 
    for (int i = bin.size() - 1;i >= 0;--i) 
     if (bin[i] == '1')d += pow(2, i); 
    return d; 
} 

void path(int x = 0,int y = 0) 
{ 

    if(x>n-1||y>n-1) 
    return; 
    else if(x==n-1&&y==n-1) 
    { 
     tmp.push_back(field[x][y]); 
     reverse(tmp.begin(), tmp.end()); 
     de.push_back(dec(tmp)); 
     tmp.clear(); 
    } 
    else 
    { 
     tmp.push_back(field[x][y]); 
     path(x + 1, y); 
     path(x, y + 1); 
    } 
} 

int main() 
{ 
    cin >> n; 
    rep(i,n)rep(j,n) 
     cin >> field[i][j]; 
    path(); 
    cout << *max_element(de.begin(), de.end()); 
    return 0; 
} 

Исследуемый образец я получил от моего учителя

5 

-1 -0 -1 1 0  
0 0 -1 0 1 
0 0 -1 0 1 
1 0 -0 -1 1 
1 1 0 -1 -0 

Который должен напечатать 374, который 101110010 (путь, который я с пометкой из теста), но когда я использую его на моем коде это печать 314, как этот путь.

-1 0 1 1 0  
-0 0 1 0 1 
-0 0 1 0 1 
-1 0 0 1 1 
-1 -1 -0 -1 -0 

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

Answer 1

Очистка пути от цели предотвратит поиск пути, разветвленного от середины пути. Вы должны использовать pop_back, чтобы вернуться.

Попробуйте это:

void path(int x = 0,int y = 0) 
{ 

    if(x>n-1||y>n-1) 
    return; 
    else if(x==n-1&&y==n-1) 
    { 
     tmp.push_back(field[x][y]); 
     reverse(tmp.begin(), tmp.end()); 
     de.push_back(dec(tmp)); 
     reverse(tmp.begin(), tmp.end()); 
     tmp.pop_back(); 
    } 
    else 
    { 
     tmp.push_back(field[x][y]); 
     path(x + 1, y); 
     path(x, y + 1); 
     tmp.pop_back(); 
    } 
} 

Обратите внимание, что обратная должна быть обращена вспять, чтобы снова сделать путь после возвращения правильно.