Witam,
Mam takie problem mam na zaliczenie labkow napisac kilka programow i z jednym z nich mam problem mianowicie takim:
Napisac program znajdujacy droge skoczka szachowego na szachownicy (skoczek musi znalezc sie na wszystkich polach bedac na ka dym polu tylko jeden raz).
Dane wejsciowe: rozmiar szachownicy oraz poczatkowa pozycja skoczka.
Oto mój kod, który naskrobałem:
#include <iostream>
#include <iomanip>
using namespace std;
// Prototypy funkcji
void InicjacjaTablicy(int **board, int xRozmiar, int yRozmiar);
void WyswietlTablice(int **board, int xRozmiar, int yRozmiar);
bool KonikSzachowy(int **board, int xx, int yy, int xRozmiar, int yRozmiar, int moveNum);
bool MoveIsValid(int **board, int xx, int yy, int xRozmiar, int yRozmiar);
int main()
{
int xRozmiar, yRozmiar, xx, yy;
int **board;
// Pętla dopoki uzytkownik nie wprowadzi rozmiarów szachownicy
do
{
cout << "Wprowadz wymiary tablicy(oddzielajac spacja):";
cin >> xRozmiar >> yRozmiar;
} while ((xRozmiar < 1) || (yRozmiar < 1));
do
{
cout << "Wprowadz punkt startowy x wieksze od 1-poziomo:";
cin >> xx;
} while ((xx > xRozmiar) || (xx < 1));
do
{
cout << "Wprowadz punkt startowy y wieksze od 1-pionowo:";
cin >> yy;
} while ((yy > yRozmiar) || (yy < 1));
cout << "Wymiary tablicy:" << xRozmiar << "X" << yRozmiar << endl;
cout << "Punkty startowe: X:" << xx << "/Y:" << yy << endl;
xx--;
yy--;
cout << "---------------------------------------------------" << endl << endl;
board = new int *[xRozmiar];
int **temp = board;
for (int a = 0; a < xRozmiar; a++)
{
*temp = new int[yRozmiar];
(temp)++;
}
InicjacjaTablicy(board, xRozmiar, yRozmiar);
WyswietlTablice(board, xRozmiar, yRozmiar);
cout << endl << "---------------------------------------------------" << endl;
cout << "Uruchamianie Konik Szachowy..." << endl;
if (KonikSzachowy(board, xx, yy, xRozmiar, yRozmiar, 1))
{
cout << "Rozwiazanie znaleziono: " << endl << endl;
WyswietlTablice(board, xRozmiar, yRozmiar);
}
else
{
cout << "Nie znaleziono rozwiazania." << endl << endl;
WyswietlTablice(board,xRozmiar,yRozmiar);
}
// Free up memory allocated for board.
for(int i = 0; i < xRozmiar; i++)
{
delete [] (*board);
(board)++;
}
cout << "Nacisnij klawisz aby kontynuowac...";
cin.ignore(1000,'\n');
cin.get();
return 0;
}
// Funkcja inicjująca tablice
void InicjacjaTablicy(int **board, int xRozmiar, int yRozmiar)
{
int x, y;
for (x = 0; x < xRozmiar; x++)
{
for (y = 0; y < yRozmiar; y++)
{
board[x][y] = 0;
}
}
}
// Wystwietl tablice
void WyswietlTablice(int **board, int xRozmiar, int yRozmiar)
{
int x, y;
for (x = 0; x < xRozmiar; x++)
{
for (y = 0; y < yRozmiar; y++)
{
cout << setw(3) << board[x][y];
}
cout << endl;
}
}
bool MoveIsValid(int **board, int xx, int yy, int xRozmiar, int yRozmiar)
{
if ((xx < 0) || (xx >= xRozmiar))
{
return false;
}
if ((yy < 0) || (yy >= yRozmiar))
{
return false;
}
if (board[xx][yy] != 0)
{
return false;
}
return true;
}
// Szkoczek Szachowy algorytm.
bool KonikSzachowy(int **board, int xx, int yy, int xRozmiar, int yRozmiar, int moveNum)
{
if (!MoveIsValid(board, xx, yy, xRozmiar, yRozmiar))
{
return false;
}
board[xx][yy] = moveNum;
if ((xRozmiar * yRozmiar) == moveNum)
{
return true;
}
cout << "KS: "<< yy << ", " << xx << ", " << moveNum << endl;
if (!KonikSzachowy(board, (xx - 1), (yy - 2), xRozmiar, yRozmiar, (moveNum + 1)))
if (!KonikSzachowy(board, (xx - 2), (yy - 1), xRozmiar, yRozmiar, (moveNum + 1)))
if (!KonikSzachowy(board, (xx - 2), (yy + 1), xRozmiar, yRozmiar, (moveNum + 1)))
if (!KonikSzachowy(board, (xx - 1), (yy + 2), xRozmiar, yRozmiar, (moveNum + 1)))
if (!KonikSzachowy(board, (xx + 1), (yy + 2), xRozmiar, yRozmiar, (moveNum + 1)))
if (!KonikSzachowy(board, (xx + 2), (yy + 1), xRozmiar, yRozmiar, (moveNum + 1)))
if (!KonikSzachowy(board, (xx + 2), (yy - 1), xRozmiar, yRozmiar, (moveNum + 1)))
if (!KonikSzachowy(board, (xx + 1), (yy - 2), xRozmiar, yRozmiar, (moveNum + 1)))
return false;
}
SCREAN Z PROBLEMEM: http://img713.imageshack.us/img713/5862/obraztd.png
Opis problemu:
Problem polega na tym, że kolejność ruchow jest wykonywana poprawnie do 20 potem cos mi sie sypie i znowu wywala 18,19 itd..problem pojawia sie tez na innych wymirach tablicy, scieram sie nad tym od poand 3 godzin i nie mam pojecia jak to rozwiazac. Dla zobrazowania problemu screean powyzej. Prosze o pomoc...bo nie potrafie sobie z tym poradzic..