Zadanie z Backtrackingu
Logowanie
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zapomniałem hasła
» Forum » Programowanie » [C, C++] Szukam pomocy

Zadanie z Backtrackingu

Ostatnio zmodyfikowano 2018-02-01 23:27
Autor Wiadomość
Mati3k01
Temat założony przez niniejszego użytkownika
Zadanie z Backtrackingu
» 2018-01-19 21:31:52

https://main2.edu.pl/c​/konkurs-podstaw-algorytmiki/p​/kul/

Witam, siedziałem nad tym zadaniem dobre pare godzin, udało mi się napisać tylko bardzo brutowe rozwiązania, które i tak nie działały.. Największy problem mam chyba z reprezentacją danych być może da się utworzyć jakieś tablice pomocnicze, które przyśpieszą algorytm. Druga sprawa to czyszczenie liczb za pomocą "grawitacji" nie jestem pewien czy da się tu wymyślić coś lepszego niż brutowe czyszczenie.
P-168845
darko202
» 2018-01-24 07:46:59
1.
myślę, że najbardziej pasuje tu zastosowanie algorytmu drzewa gier
http://www.algorytm.org/inne​/drzewa-gier.html
przykład jest do innej gry, ale opisana idea postępowania jest rozwiązaniem które musisz wykonać.
2.
co do problemów z odnalezieniem się w kodzie to najlepszą metoda jest używanie techniki minimalizacji kodu tzn. (małe kawałki które są łatwe do sprawdzenia np. funkcja, klasa)
oraz techniki debugowania kodu (sprawdzaniu stanu wszystkich zmiennych w każdej linii)
3.
zaprezentuj Twoje rozwiązanie nawet jeśli jest niedoskonałe,
to może będziemy mogli jakoś Ci pomóc - daj nam szanse :)

Powodzenia


 
P-168959
Mati3k01
Temat założony przez niniejszego użytkownika
» 2018-01-28 15:24:59
C/C++
const int SIZE = 8;

struct best_sequence
{
    int x1;
    int y1;
    int x2;
    int y2;
};

bool operator <( const best_sequence & a, const best_sequence & b ) {
   
    if( a.x1 < b.x1 )
         return true;
    else if( a.x1 == b.x1 )
    {
        if( a.y1 < b.y1 )
             return true;
        else if( a.y1 == b.y1 )
        {
            if( a.x2 < b.x2 )
                 return true;
            else if( a.x2 == b.x2 )
            {
                if( a.y2 < b.y2 )
                     return true;
                else
                     return false;
               
            }
            else
                 return false;
           
        }
        else
             return false;
       
    }
    else
         return false;
   
}

struct mvs //moves
{
    //1st
    int y1;
    int x1;
   
    //2nd
    int y2;
    int x2;
   
    operator best_sequence()
    {
        best_sequence temp;
        temp.x1 = x1; temp.y1 = y1;
        temp.x2 = x2; temp.y2 = y2;
        return temp;
    }
   
};

struct coords
{
    int x;
    int y;
};

int countBalls( std::vector < std::vector < char >> & data )
{
    int counter = 0;
    for( int i = 0; i < data.size(); i++ )
    for( int j = 0; j < data.size(); j++ )
    if( data[ i ][ j ] != '.' )
         counter++;
   
    return counter;
}

std::vector < mvs > possibleMoves( std::vector < std::vector < char >> & board )
{
    std::vector < mvs > temp_vec;
    mvs temp_struct;
    for( int i = 0; i < board.size(); i++ ) //vertically --
    for( int j = 0; j < board.size() - 1; j++ )
    if( board[ i ][ j ] != '.' && board[ i ][ j + 1 ] != '.' )
    {
        temp_struct = { i, j, i, j + 1 };
        temp_vec.push_back( temp_struct );
    }
   
    for( int i = 0; i < board.size() - 1; i++ )
    for( int j = 0; j < board.size(); j++ )
    if( board[ i ][ j ] != '.' && board[ i + 1 ][ j ] != '.' ) //horizontally |
    {
        temp_struct = { i, j, i + 1, j };
        temp_vec.push_back( temp_struct );
    }
   
    return temp_vec;
}

void simplifyRows( std::vector < std::vector < char >> & board, const mvs & move )
{
   
    std::vector < coords > toRemove;
   
    if( move.y1 == move.y2 )
    {
        int counter = 1;
        for( int i = 0; i < board.size() - 1; i++ )
        {
            if( board[ move.y1 ][ i ] == board[ move.y1 ][ i + 1 ] )
                 counter++;
            else
            {
                for( int j = i - counter + 1; j <= i; j++ )
                     board[ move.y1 ][ j ] = '.';
               
                counter = 1;
            }
        }
    }
    else
    {
        int counter = 1;
        for( int i = 0; i < board.size() - 1; i++ )
        {
            if( board[ move.y1 ][ i ] == board[ move.y1 ][ i + 1 ] )
                 counter++;
            else
            {
                for( int j = i - counter + 1; j <= i; j++ )
                     board[ move.y1 ][ j ] = '.';
               
                counter = 1;
            }
        }
       
        counter = 1;
        for( int i = 0; i < board.size() - 1; i++ )
        {
            if( board[ move.y2 ][ i ] == board[ move.y2 ][ i + 1 ] )
                 counter++;
            else
            {
                for( int j = i - counter + 1; j <= i; j++ )
                     board[ move.y2 ][ j ] = '.';
               
                counter = 1;
            }
        }
    }
   
}

void simplifyCols( std::vector < std::vector < char >> & board, const mvs & move )
{
   
    if( move.y1 == move.y2 )
    {
        int counter = 1;
        for( int i = 0; i < board.size() - 1; i++ )
        {
            if( board[ i ][ move.x1 ] == board[ i + 1 ][ move.x1 ] )
                 counter++;
            else
            {
                if( counter >= 3 )
                {
                    for( int j = i - counter + 1; j >= i; j++ )
                         board[ j ][ move.x1 ] = '.';
                   
                }
                counter = 1;
            }
        }
       
        counter = 1;
        for( int i = 0; i < board.size() - 1; i++ )
        {
            if( board[ i ][ move.x2 ] == board[ i + 1 ][ move.x2 ] )
                 counter++;
            else
            {
                if( counter >= 3 )
                {
                    for( int j = i - counter + 1; j >= i; j++ )
                         board[ j ][ move.x2 ] = '.';
                   
                }
                counter = 1;
            }
        }
    }
    else //swap was made vertically
    {
        int counter = 1;
        for( int i = 0; i < board.size() - 1; i++ )
        {
            if( board[ i ][ move.x1 ] == board[ i + 1 ][ move.x1 ] )
                 counter++;
            else
            {
                if( counter >= 3 )
                {
                    for( int j = i - counter + 1; j >= i; j++ )
                         board[ j ][ move.x1 ] = '.';
                   
                }
                counter = 1;
            }
        }
    }
}

void gravityDrop( std::vector < std::vector < char >> & board )
{
    //to do
    for( int i = 0; i < board.size(); i++ )
    for( int j = 0; j < board.size() - 1; j++ )
    if( board[ j ][ i ] != '.' && board[ j + 1 ][ i ] == '.' )
         std::swap( board[ j ][ i ], board[ j + 1 ][ i ] );
   
}

std::vector < std::vector < char >> simplify( std::vector < std::vector < char >> board, const mvs & move )
{
    //std::vector<coords> toRemoveRows = simplifyRows(board,move);
    //std::vector<coords> toRemoveCols = simplifyCols(board, move);
   
    simplifyRows( board, move );
    simplifyCols( board, move );
   
    /*for(coords & crds : toRemoveCols)
            board[crds.y][crds.x] = '.';
        for(coords & crds : toRemoveRows)
            board[crds.y][crds.x] = '.';*/
   
   
    gravityDrop( board );
   
    return board;
}

std::vector < std::vector < char >> makeMove( std::vector < std::vector < char >> board, const mvs & move )
{
    std::swap( board[ move.y1 ][ move.x1 ], board[ move.y2 ][ move.x2 ] );
   
   
    return simplify( board, move );
}

std::vector < best_sequence > solve( std::vector < std::vector < char >> board, std::vector < best_sequence > moves = std::vector < best_sequence >(), int level = 0 )
{
    int score = countBalls( board );
    std::cout << level << std::endl;
    if( score == 0 )
         return moves;
   
    if( level == 8 )
         return std::vector < best_sequence >();
    else
    {
        //let there be hell
        std::vector < best_sequence > movesList;
        for( mvs move: possibleMoves( board ) )
        {
            std::vector < std::vector < char >> newBoard = makeMove( board, move );
            int newScore = countBalls( newBoard );
            if( newScore == score )
                 continue;
           
            movesList.push_back( move );
            std::vector < best_sequence > newMoves = solve( newBoard, movesList, level + 1 );
            movesList.pop_back();
           
            if( newMoves.size() < movesList.size() )
                 movesList = newMoves;
            else if( newMoves.size() == movesList.size() && std::lexicographical_compare( newMoves.begin(), newMoves.end(), movesList.begin(), movesList.end() ) )
                 movesList = newMoves;
           
        } //loop end
       
        if( movesList.size() > 0 )
             return movesList;
        else
             return std::vector < best_sequence >();
       
    } //else end
}


int main( int argc, const char * argv[] ) {
   
    using namespace std;
    std::vector < std::vector < char >> data;
   
    for( int i = 0; i < SIZE; i++ )
    {
        vector < char > temp( SIZE );
        for( int j = 0; j < SIZE; j++ )
             cin >> temp[ j ];
       
        data.push_back( temp );
    }
   
    vector < best_sequence > result = solve( data );
    cout << result.size() << endl;
    for( best_sequence & x: result )
         cout << x.x1 << " " << x.y1 << " " << x.x2 << " " << x.y2 << endl;
   
    return 0;
}

Wyszło mi coś takiego ale problem polega na tym, że ta funkcja nigdy się nie kończy a cout w funkcji wstawiłem tylko po to, żeby sprawdzić jak wyglądają zagłębienia w rekurencji.
Ale też nie wydaje mi się żeby istniało jakieś rozwiązanie znacznie przycinające drzewo przeszukiwań, z resztą w treści jawnie piszą, że maksymalny poziom zagłębienia to 8

EDIT: napewno gravityDrop nie działa poprawnie.. postaram się to naprawić.

C/C++
void gravityDrop( std::vector < std::vector < char >> & board )
{
    //to do
    for( int a = 0; a < board.size(); a++ )
    for( int i = board.size() - 2; i >= 0; i-- )
    for( int j = 0; j < board.size(); j++ )
    if( board[ i ][ j ] != '.' && board[ i + 1 ][ j ] == '.' )
         std::swap( board[ i ][ j ], board[ i + 1 ][ j ] );
   
}
P-169083
darko202
» 2018-01-29 11:24:36
1.
Nie zaprezentowałeś algorytmu, który chcesz realizować.
Przedstawiony kod :
* nie zawiera komentarza
* zmienne nie są opisowe (samodokumentujące kod)

dlatego trudno się zorientować co i jak to próbujesz zrobić ? 
 
2.
zamieściłeś dwie wersje void gravityDrop(
ta w programie nie posiada linii
 for( int a = 0; a < board.size(); a++ )
linia ta wydaje się niepotrzebna

3.
w tej funkcji badasz
if( board[ i ][ j ] != '.' && board[ i + 1 ][ j ] == '.' )

czyli po osi i
porządkujemy linię dlatego mogłoby być
 for( int j = 0; j < board.size(); j++ ) // powtarzamy dla kolejnego rzędu
    for( int i = board.size() - 2; i >= 0; i-- ) // grawitacja dla kolejnej linii
      if( board[ i + 1 ][ j ] == '.' && board[ i ][ j ] != '.' )
         std::swap ...

4.
w funkcji nie widać w niej błędu
wydaje się że gdybyś użył zmiennych x, y zamiast i, j przypominałoby układ kartezjański znany z matematyki
wtedy, gdybyśmy wykorzystywali I ćwiartkę y (czyli j) by rosły

nie mogłem znaleźć miejsca gdzie wypełniasz board 
sprawdź, czy nie robisz tego odwrotnie 

to by tłumaczyło dlaczego nie działa

5.
nie widziałem abyś gdzieś wyświetlał stan swojego board tzn .funkcja printBoard
jest to najprostsza technika debugowania swojego programu

przydałaby Ci się zorientować co się dzieje ?

6.
using namespace std;
użyj w nagłówku pliku a nie metodzie main

7.
>> problem polega na tym, że ta funkcja nigdy się nie kończy
z powodu tego co pisałem w punkcie 1.
trudno wskazać co robisz źle, ale

realizowany algorytm wyglądać powinien tak
zadanie :
* mamy tablicę 8x8 punktów,
* przesuwamy wartości z sąsiednich punktów (osiami - x,y)
* jeśli są min 3 takie same elementy w rzędzie to usuwamy je
* w usunięciu mogą brać udział jednocześnie obie osie
* brana jest pod uwagę grawitacja względem jednej osi   
* czynność powtarzamy do sytuacji gdy brak jest
* mamy osiągnąć sytuację oczyszczenia tablicy

* wygrywa najkrótsza sekwencja
* ograniczeniem jest warunek, że długość sekwencji nie może przekroczyć 8 ruchów usunięcia

Algorytm
A.
Uwzględniamy, że każdy punkt przesuwamy w dwóch kierunkach (np. dół, lewo)
to daje nam zbiór 7x2 + 2x7x1 możliwe przesunięcia
 
zauważmy, że jeśli w przesuwanych punktach jest ta sama wartość to jeden z nich możemy wyeliminować (w jednym z kierunków) co ogranicza zbiór

po tym kroku mamy zbiór możliwych ruchów - czyli gałęzie drzewa gry - badany poziom

B.
dla danej gałęzi
Potrzebujemy algorytmu, który po przesunięciu sprawdzi, co możemy z tablicy usunąć ? (po wykonaniu przesunięcia) 
 
jeśli możemy coś usunąć  to usuwamy, i wracamy do p A algorytmu rozbudowując kolejny poziom gałęzi gry
(uwzględniając warunek 8 poziomów max.)

jeśli nie to tą gałąź można usunąć, gdyż nie prowadzi do wygranej

C. Na zakończeniu sprawdzamy wszystkie dostępne rozwiązania i wybieramy najlepsze i te prezentujemy


U Ciebie nie widzę zarysu czegoś takiego :(
ale może to tylko moja wrodzona ślepota :)

Powodzenia !
 


 
P-169115
Mati3k01
Temat założony przez niniejszego użytkownika
» 2018-01-29 23:16:58
Wziąłem pod uwagę twoje wskazówki, teraz algorytm już działa ale jeszcze ma jakieś usterki, mam dużo przekroczonych limitów czasowych(80%) a reszta to 50/50 testy pozytywne i negatywne, test z przykładu przechodzi bez problemu, od razu jak będę miał możliwość to wrzucę kod z komentarzami.
P-169126
Mati3k01
Temat założony przez niniejszego użytkownika
» 2018-01-30 09:07:20
C/C++
#include <iostream>
#include <vector>
#include <algorithm>

const int SIZE = 8;

struct best_sequence //najlepsze ruchy
{
    int x1;
    int y1;
    int x2;
    int y2;
};

bool operator <( const best_sequence & a, const best_sequence & b ) { //porównanie potrzebne do porzadku leksykograficznego
   
    if( a.x1 < b.x1 )
         return true;
    else if( a.x1 == b.x1 )
    {
        if( a.y1 < b.y1 )
             return true;
        else if( a.y1 == b.y1 )
        {
            if( a.x2 < b.x2 )
                 return true;
            else if( a.x2 == b.x2 )
            {
                if( a.y2 < b.y2 )
                     return true;
                else
                     return false;
               
            }
            else
                 return false;
           
        }
        else
             return false;
       
    }
    else
         return false;
   
}

struct mvs //struktura do swapów
{
    //1st group
    int y1;
    int x1;
   
    //2nd group
    int y2;
    int x2;
   
    operator best_sequence() //rzutowanie jej na strukture best_sequence
    {
        best_sequence temp;
        temp.x1 = y1; temp.y1 = x1;
        temp.x2 = y2; temp.y2 = x2;
        return temp;
    }
   
};

struct coords
{
    int x;
    int y;
};

void print( std::vector < std::vector < char >> & board ) //wyswietla
{
    for( int i = 0; i < SIZE; i++ )
    {
        for( int j = 0; j < SIZE; j++ )
             std::cout << board[ i ][ j ];
       
        std::cout << std::endl;
    }
   
}

int countBalls( std::vector < std::vector < char >> & data ) //zlicza pilki
{
    int counter = 0;
    for( int i = 0; i < data.size(); i++ )
    for( int j = 0; j < data.size(); j++ )
    if( data[ i ][ j ] != '.' )
         counter++; //kazdy znak inny niz kropka to kolejna pilka
   
    return counter;
}

std::vector < mvs > possibleMoves( std::vector < std::vector < char >> & board ) //generuje mozliwe ruchy
{
    std::vector < mvs > temp_vec;
    mvs temp_struct;
    for( int i = 0; i < board.size(); i++ )
    for( int j = 0; j < board.size() - 1; j++ )
    if( board[ i ][ j ] != '.' && board[ i ][ j + 1 ] != '.' ) //pionowo(co do warunku nie jestem pewien czy mamy zamieniac tylko pilki czy mozemy swapowac takze w sytuacji gdy jeden ze znakow to pilka)
    {
        temp_struct = { i, j, i, j + 1 }; //dodajemy do vectora koordynaty s
        temp_vec.push_back( temp_struct );
    }
   
    for( int i = 0; i < board.size() - 1; i++ )
    for( int j = 0; j < board.size(); j++ )
    if( board[ i ][ j ] != '.' && board[ i + 1 ][ j ] != '.' ) //poziomo i tu takze nie wiem jak z warunkiem
    {
        temp_struct = { i, j, i + 1, j };
        temp_vec.push_back( temp_struct );
    }
   
    return temp_vec;
}

std::vector < coords > simplifyRows( std::vector < std::vector < char >> & board, const mvs & move ) //upraszcza wiersze jesli wystepuja wiecej niz 3 takie same pilki pod rzad
{
    std::vector < coords > toRemove;
   
    for( int i = 0; i < SIZE; i++ )
    {
        int counter = 1;
        for( int j = 0; j < SIZE - 1; j++ )
        {
            if( board[ j ][ i ] != '.' && board[ j ][ i ] == board[ j + 1 ][ i ] )
                 counter++;
            else
                 counter = 1;
           
            if( counter >= 3 )
            for( int k = 0; k < counter; k++ )
            toRemove.push_back( { i, j - k + 1 } ); //wspolrzedne zapisujemy do vectora z koordynatami
        }
    }
   
    return toRemove;
}

std::vector < coords > simplifyCols( std::vector < std::vector < char >> & board, const mvs & move ) //analogicznie do poprzedniej funkcji tylko ze upraszcza kolumny
{
    std::vector < coords > toRemove;
   
    for( int i = 0; i < SIZE; i++ )
    {
        int counter = 1;
        for( int j = 0; j < SIZE - 1; j++ ) //rows
        {
            if( board[ i ][ j ] != '.' && board[ i ][ j ] == board[ i ][ j + 1 ] )
                 counter++;
            else
                 counter = 1;
           
            if( counter >= 3 )
            for( int k = 0; k < counter; k++ )
            toRemove.push_back( { j - k + 1, i } );
        }
    }
   
    return toRemove;
}

void gravityDrop( std::vector < std::vector < char >> & board )
{
   
    /*for(int a = 0; a < SIZE; a++)
            for(int i = board.size()-2; i >= 0; i--)
                for(int j = 0; j < board.size(); j++)
                    if(board[i][j] != '.' && board[i+1][j] == '.')
                        std::swap(board[i][j], board[i+1][j]);*/
   
    for( int row = 0; row < SIZE; row++ )
    for( int col = 0; col < SIZE; col++ ) //nowe gravityDrop "zrzuca" pilki w dol jesli okaze sie ze jest pod nimi wolna przestrzen "pilki"
    if( board[ SIZE - row - 1 ][ col ] == '.' )
    {
        for( int up_row = SIZE - row - 1; up_row >= 0; up_row-- )
        {
            if( board[ up_row ][ col ] != '.' )
            {
                board[ SIZE - row - 1 ][ col ] = board[ up_row ][ col ];
                board[ up_row ][ col ] = '.';
                break;
            }
        }
    }
}

std::vector < std::vector < char >> simplify( std::vector < std::vector < char >> board, const mvs & move )
{
    using std::cout;
    using std::endl;
   
    std::vector < coords > toRemoveRows = simplifyRows( board, move );
    std::vector < coords > toRemoveCols = simplifyCols( board, move ); //podmieniamy pozycje zwrocone przez obie funkcje na kropki
   
    for( coords & crds: toRemoveCols )
    {
        //cout << "COLS:" << crds.x << " " << crds.y << endl;
        board[ crds.y ][ crds.x ] = '.';
    } //podmiana
    for( coords & crds: toRemoveRows )
    {
        //cout << "ROWS:" << crds.x << " " << crds.y << endl;
        board[ crds.y ][ crds.x ] = '.';
    } //podmiana
   
    if( toRemoveCols.size() > 0 || toRemoveRows.size() > 0 ) //jesli rzeczywiscie byly jakies pilki do redukcji wykonujemy gravity drop
         gravityDrop( board );
   
    return board;
}

std::vector < std::vector < char >> makeMove( std::vector < std::vector < char >> board, const mvs & move )
{
    std::swap( board[ move.y1 ][ move.x1 ], board[ move.y2 ][ move.x2 ] ); //swap
   
   
    return simplify( board, move ); //zwraca zredukowana tablice po wykonaniu ruchu
}

std::vector < best_sequence > solve( std::vector < std::vector < char >> board, std::vector < best_sequence > moves = std::vector < best_sequence >(), int level = 0 )
{
    int score = countBalls( board ); //liczy ilosc pozostalych kulek
    if( score == 0 )
         return moves; //jesli nie zostala zadna zwroc obecna sekwencje ruchow
   
    if( level == 8 ) //jesli doszlismy do 8 poziomu zaglebienia zwracamy pusta sekwencje(nie mozemy wykonac wiecej ruchow)
         return std::vector < best_sequence >();
    else // w innym przypadku
    {
       
        std::vector < best_sequence > bestMoves( 9 ); //tworzymy vector do najlepszych sekwencji
        for( mvs move: possibleMoves( board ) ) //generujemy vector dostepnych ruchow
        {
            std::vector < std::vector < char >> newBoard = makeMove( board, move ); //wykonujemy nowy ruch
            int newScore = countBalls( newBoard ); //jesli ruch nie zredukowal zadnej pilki
            if( newScore == score )
                 continue; //szukamy nowego ruchu
           
            moves.push_back( move ); //jesli jednak zredukowal nam jakies pilki/pilki
            std::vector < best_sequence > newMoves = solve( newBoard, moves, level + 1 ); //bedziemy wykonywali te sama funkcje tylko dla zredukowanej juz tablicy
            //dopiszemy tez do sekwencji ruchow ruch ktory zredukowal tablice
            moves.pop_back(); //wychodzimy z funkcji wiec usuwamy ten ruch
           
            if( newMoves.size() > 0 ) //jesli dostaniemy jakies nowe ruchy
            {
               
                if( newMoves.size() < bestMoves.size() ) //porownojemy je z obecna najlepsza sekwencja
                     bestMoves = newMoves;
                else if( newMoves.size() == bestMoves.size() && std::lexicographical_compare( newMoves.begin(), newMoves.end(), bestMoves.begin(), bestMoves.end() ) )
                     bestMoves = newMoves; //przypisujemy nowa sekwencje
               
            }
           
        } //loop end
       
        return bestMoves;
       
    } //else end
}


int main( int argc, const char * argv[] ) {
   
    using namespace std;
    std::vector < std::vector < char >> data;
    //read
    for( int i = 0; i < SIZE; i++ )
    {
        vector < char > temp( SIZE ); //wczytywanie(jest poprawne sprawdzalem za pomoca print)
        for( int j = 0; j < SIZE; j++ )
        {
            cin >> temp[ j ];
            /*temp[j] = char(rand() % 3 + 65);
                        if(temp[j] == (char)65)
                            temp[j] = '.';*/
        }
        data.push_back( temp );
    } //at least we got pretty good input
    //gravityDrop(data);
    //print(data);
   
    vector < best_sequence > result = solve( data ); //wyswietlanie wynikow
    cout << result.size() << endl;
    for( best_sequence & x: result )
         cout << x.x1 + 1 << " " << x.y1 + 1 << " " << x.x2 + 1 << " " << x.y2 + 1 << endl;
   
    return 0;
}

EDIT:Kiedy użyłem warunku przy generowaniu możliwych ruchów takiego, że tylko jedno z miejsc musi mieć piłkę to ilość błędów w sprawdzarce spadła, ale wciąż w każdym teście przekraczam o max 1s dla testu z limitem 17/20s i jakieś ułamki sekund dla testów z limitem 1 lub 2s
P-169132
darko202
» 2018-01-30 13:53:18
1.
zastanawia mnie, gdy funkcja zwraca zmienną lokalną
np.
C/C++
vector < mvs > possibleMoves( vector < vector < char >> & board ) //generuje mozliwe Ruchy
{
    vector < mvs > temp_vec;
    ...
   
    return temp_vec;
}
 co to oznacza ? np.  w linii
  for( mvs move: MozliweRuchy( board ) ) //generujemy vector dostepnych Ruchow

 tworzona jest kopia zmiennej zwracanej z tej funkcji
  powtarzamy to N razy

identyczna sytuacja powtarza się w innych funkcjach 

zakładam że mogę się mylić, ale w kursach jakoś nie było to polecane.
Coś było z tym nie tak.  :( 

ja bym realizował to inaczej ? 

  2.
 
C/C++
for( mvs move: possibleMoves( board ) ) //generujemy vector dostepnych Ruchow
{
    ....
    int newScore
    w każdej petli tworzysz nową zmienną 
 
 to też powtarza się w innych funkcjach
:(
 
 3.
using namespace std;
użyj w nagłówku pliku a nie metodzie main, bo deklaracja
vector < mvs > possibleMoves( vector < vector < char >> & board )
jest czytelniejsza niż
std::vector < mvs > possibleMoves( std::vector < std::vector < char >> & board )
  
zwłaszcza w skali całego programu


4.
>> ilość błędów w sprawdzarce spadła  
nie sugeruj się tym - z mojego doświadczenia to nic nie znaczy

5.
widzę, ze
  if( board[ i ][ j ] != '.' && board[ i ][ j ] == board[ i ][ j + 1 ] )
masz w obu metodach  UproszczKolumne, UproszczWiersz

myslę, ze coś z tym jest nie tak ?

poza tym, że niespełnione są warunki zadania :
* jeśli są min 3 takie same elementy w rzędzie to usuwamy je
* w usunięciu mogą brać udział jednocześnie obie osie

czyli chyba powinna byc jedna metoda

6.
int score = countBalls( board ); //liczy ilosc pozostalych kulek
?
z tego można by zrezygnować
* dodając takie pole w board
* licząc ilość kul na starcie
* redukując po każdym uproszczeniu

7.
łatwiej się czyta gdy używa się standadu nazewnictwa np.
funkcje, struktury  - duza litera 
zmienne z małej

8.
w obu metodach  UproszczKolumne, UproszczWiersz przekazujesz
const mvs & move
nie wykorzystujesz jej,

choć nie jest to zły pomysł
bo interesują nas chyba uproszczenia wokół
//1st group
//2nd group

dla punktu wykonujemy sprawdzenia w 4 kierunkach (lewo, prawo, góra, dół)

trzeba wykonać mniej sprawdzeń

9.
zastanawia mnie linia
std::vector < best_sequence > newMoves = solve( newBoard, moves, level + 1 );
 
bo w wektorze który jakoś jest liniowy próbujesz zmieścić graf gry
zastanawia mnie to :)
tzn. jakoś mnie to niepokoi :(
nie widzę jak można osiągnąć realizowany cel

Powodzenia !
P-169134
Mati3k01
Temat założony przez niniejszego użytkownika
» 2018-01-30 15:44:32
Co do possibleMoves to fakt, mógłbym to generować wewnątrz solve, wtedy nie będę musiał tworzyć potężnych tymczasowych vectorów, żeby skopiować możliwe swapy z funkcji do pętli zakresowej, a nad resztą też popracuję ;)
P-169136
« 1 » 2
  Strona 1 z 2 Następna strona
» Forum » Programowanie » [C, C++] Szukam pomocy
© Wszelkie prawa zastrzeżone 2005-2025